Problem p03108 (python)

Fixed submission:
# ABC 120 D

from collections import deque

class UnionFind():
    # n : 要素数
    def __init__(self, n):
        self.n = n
        # root[x] < 0 ならそのノードが根かつその値が木の要素数
        # root[x] > 0 ならそのノードが根
        self.root = [-1] * (n+1)
        # 木の高さの管理
        self.rnk = [0] * (n+1)

    # x が所属するグループの根を返す
    def findRoot(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findRoot(self.root[x])  # 経路圧縮
            return self.root[x]

    # x と y がそれぞれ所属するグループを結合する
    def unite(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            # 既に同じグループに所属していれば何もしない
            return
        elif self.rnk[x] > self.rnk[y]:    # x の方が高さがある場合
            self.root[x] += self.root[y]   # x の要素数に y の要素数を足す
            self.root[y] = x               # y の親を x にする
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    def count(self, x):
        return -self.root[self.findRoot(x)]

def resolve():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    AB = AB[::-1]

    ret = []

    uf = UnionFind(N)

    for a, b in AB:
        if uf.isSameGroup(a-1, b-1):
            ret.append(0)
        else:
            ret.append(uf.count(a-1) * uf.count(b-1))
            uf.unite(a-1, b-1)

    ans = 0
    for i in range(M-1, -1, -1):
        ans += ret[i]
        print(ans)

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
# ABC 120 D

from collections import deque

def resolve():
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    par = [i for i in range(N+1)]

    nums = [1] * (N+1)  # i を根に持つ要素の数

    # x の根を求める
    def root(x):
        if par[x] == x:
            return x
        tmp = par[x]
        par[x] = root(par[x])  # 経路圧縮
        nums[tmp] -= 1
        nums[par[x]] += 1
        return par[x]

    # x と y の属する集合を併合
    # 便利になった数を返す
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return
        par[x] = y
        conv = nums[x] * nums[y]
        nums[y] += nums[x]
        nums[x] = 0
        return conv

    # A[M-1] から順に橋をかけていく
    answers = [0] * M
    answers[M-1] = N*(N-1) // 2

    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        if root(a) == root(b):  # 既に同じグループにいれば何もしない
            continue

        # 違うグループにいる場合はグループ同士を結合する
        conv = unite(a, b)
        answers[i-1] = answers[i] - conv

    for i in answers:
        print(i)


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
# ABC 120 D

from collections import deque

def resolve():
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    par = [i for i in range(N+1)]
    nums = [1] * (N+1)

    # x の根を求める
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])  # 経路圧縮
        return par[x]

    # x と y の属する集合を併合
    # 便利になった数を返す
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return
        par[x] = y
        conv = nums[x] * nums[y]
        nums[y] += nums[x]
        nums[x] = 0
        return conv

    # A[M-1] から順に橋をかけていく
    answers = [0] * M
    answers[M-1] = N*(N-1) // 2

    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        if root(a) == root(b):  # 既に同じグループにいれば何もしない
            continue

        # 違うグループにいる場合はグループ同士を結合する
        conv = unite(a, b)
        answers[i-1] = answers[i] - conv

    for i in answers:
        print(i)


if __name__ == "__main__":
    resolve()