Problem p02689 (python)

Fixed submission:
def solve(n, m, h, a, b):
    for j in range(m):
        a[j] -= 1
        b[j] -= 1
    E = {i:[] for i in range(n)}
    for x, y in zip(a, b):
        E[x].append(y)
        E[y].append(x)
    ans = 0
    for i in range(n):
        ok = True
        for j in E[i]:
            if h[i] <= h[j]:
                ok = False
        ans += ok
    return ans
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * m
b = [0] * m
for j in range(m):
    a[j], b[j] = map(int, input().split())
print(solve(n,m, h, a, b))

Buggy submission (verdict: Runtime Error):
def solve(n, m, h, a, b):
    for j in range(m):
        a[j] -= 1
        b[j] -= 1
    parents = [i for i in range(n)]
    def root(x):
        return x if parents[x] == x else root(parents[x])

    for a_j, b_j in zip(a, b):
        ra, rb = root(a_j), root(b_j)
        if ra != rb:
            if ra > rb:
                a_j, b_j = b_j, a_j
            parents[ra] = rb

    D = {}
    for j, pj in enumerate(parents):
        if not pj in D:
            D[pj] = []
        D[pj].append(h[j])
    ans = 0
    for k, v in D.items():
        if len(v) == 1:
            ans += 1
        else:
            v = sorted(v)
            ans += int(v[-1] > v[-2])
    return ans

n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * m
b = [0] * m
for j in range(m):
    a[j], b[j] = map(int, input().split())
print(solve(n,m, h, a, b))

Buggy submission (verdict: Runtime Error):
def solve(n, m, h, a, b):
    for j in range(m):
        a[j] -= 1
        b[j] -= 1
    parents = [i for i in range(n)]
    def root(x):
        return x if parents[x] == x else root(parents[x])

    for a_j, b_j in zip(a, b):
        ra, rb = root(a_j), root(b_j)
        if ra != rb:
            if ra > rb:
                a_j, b_j = b_j, a_j
            parents[rb] = ra

    D = {}
    for j, pj in enumerate(parents):
        if not pj in D:
            D[pj] = []
        D[pj].append(h[j])
    ans = 0
    for k, v in D.items():
        if len(v) == 1:
            ans += 1
        else:
            v = sorted(v)
            ans += int(v[-1] > v[-2])
    return ans

n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * m
b = [0] * m
for j in range(m):
    a[j], b[j] = map(int, input().split())
print(solve(n,m, h, a, b))

Buggy submission (verdict: Runtime Error):
def solve(n, m, h, a, b):
    for j in range(m):
        a[j] -= 1
        b[j] -= 1
    parents = [i for i in range(n)]
    def root(x):
        return x if parents[x] == x else root(parents[x])

    for a_j, b_j in zip(a, b):
        if root(a_j) != root(b_j):
            if a_j > b_j:
                a_j, b_j = b_j, a_j
            parents[root(b_j)] = root(a_j)

    D = {}
    for j, pj in enumerate(parents):
        if not pj in D:
            D[pj] = []
        D[pj].append(h[j])
    ans = 0
    for k, v in D.items():
        if len(v) == 1:
            ans += 1
        else:
            v = sorted(v)
            ans += int(v[-1] > v[-2])
    return ans

n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * m
b = [0] * m
for j in range(m):
    a[j], b[j] = map(int, input().split())
print(solve(n,m, h, a, b))

Buggy submission (verdict: Runtime Error):
def solve(n, m, h, a, b):
    parent = {i:i for i in range(1, n+1)}
    def root(x):
        return x if parent[x] == x else root(parent[x])

    for a_j, b_j in zip(a, b):
        if root(a_j) != root(b_j):
            if a_j > b_j:
                a_j, b_j = b_j, a_j
            parent[root(b_j)] = root(a_j)
    D = {}
    for j, pj in parent.items():
        if not pj in D:
            D[pj] = []
        D[pj].append(h[j-1])
    ans = 0
    for k, v in D.items():
        v = sorted(v)
        if len(v) == 1:
            ans += 1
        elif v[-1] > v[-2]:
            ans += 1
    return ans

n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * m
b = [0] * m
for j in range(m):
    a[j], b[j] = map(int, input().split())
print(solve(n,m, h, a, b))

Buggy submission (verdict: Runtime Error):
def solve(n, m, h, a, b):
    parent = {i:i for i in range(1, n+1)}
    def root(x):
        return x if parent[x] == x else root(parent[x])
    for a_j, b_j in zip(a, b):
        if root(a_j) != root(b_j):
            parent[root(b_j)] = root(a_j)
    D = {}
    for j, pj in parent.items():
        if not pj in D:
            D[pj] = []
        D[pj].append(h[j-1])
    ans = 0
    for k, v in D.items():
        v = sorted(v)
        if len(v) == 1:
            ans += 1
        elif v[-1] > v[-2]:
            ans += 1
    return ans

n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0] * m
b = [0] * m
for j in range(m):
    a[j], b[j] = map(int, input().split())
print(solve(n,m, h, a, b))