Problem p03356 (python)

Fixed submission:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def root(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x, y):
        return self.root(x) == self.root(y)


def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 1-origin
    union_find = UnionFind(n + 1)
    for i in range(m):
        x, y = map(int, input().split())
        union_find.unite(x, y)

    ans = 0
    for key, value in enumerate(ps, 1):
        if union_find.same(key, value):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    for key in range(1, len(ps) + 1):
        if key < len(graphs) and groups[key] == -1:
            group_id += 1
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if key < len(groups) and value < len(groups) and groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    if key >= len(groups):
        return

    global groups
    groups[key] = group_id

    for graph_key in graphs[key]:
        if graph_key < len(groups) and groups[graph_key] == -1:
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 隣接リスト作成 (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    for key in range(1, len(ps) + 1):
        if key < len(graphs) and groups[key] == -1:
            group_id += 1
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if key < len(groups) and value < len(groups) and groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    global groups
    groups[key] = group_id

    for graph_key in graphs[key]:
        if graph_key < len(graphs) and groups[graph_key] == -1:
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 隣接リスト作成 (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    for key in range(1, len(ps) + 1):
        if groups[key] == -1:
            group_id += 1
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    if key >= len(graphs):
        return

    global groups
    groups[key] = group_id

    for graph_key in graphs[key]:
        if groups[graph_key] == -1:
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 隣接リスト作成 (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    # (0, n]
    for key in range(1, len(ps) + 1):
        if groups[key] == -1:
            group_id += 1
            groups[key] = group_id
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    global groups

    for graph_key in graphs[key]:
        if groups[graph_key] == -1:
            groups[graph_key] = group_id
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()