Problem p03108 (python)

Fixed submission:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

def solve():
    N, M = map(int, input().split())
    bridges = [[int(i) - 1 for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]

    uf = UnionFind(N)
    for bridge in reversed(bridges):
        A, B = bridge
        if uf.issame(A, B):
            ans.append(ans[-1])
        else:
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
            uf.merge(A, B)
    ans.pop(-1)
    return '\n'.join(map(str, reversed(ans)))

print(solve())

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[x] += self.__size[y]
            self.__size[y] = self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

def solve():
    uf = UnionFind()
    N, M = map(int, input().split())
    bridges = [[int(i) for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]
    for A, B in reversed(bridges):
        if uf.same(A, B):
            ans.append(ans[-1])
        else:
            try:
                sa, sb = uf.size(A), uf.size(B)
                uf.union(A, B)
            except:
                sa, sb = 1, 0
            ans.append(ans[-1] - sa * sb)
    ans.pop()
    return '\n'.join(map(str, reversed(ans)))

print(solve())

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[x] += self.__size[y]
            self.__size[y] = self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

def solve():
    uf = UnionFind()
    N, M = map(int, input().split())
    bridges = [[int(i) for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]
    for A, B in reversed(bridges):
        if uf.same(A, B):
            ans.append(ans[-1])
        else:
            try:
                sa, sb = uf.size(A), uf.size(B)
                uf.union(A, B)
            except:
                sa, sb = 1, 0
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
    ans.pop()
    return '\n'.join(map(str, reversed(ans)))

print(solve())

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[x] += self.__size[y]
            self.__size[y] = self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

def solve():
    uf = UnionFind()
    N, M = map(int, input().split())
    bridges = [[int(i) for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]
    for A, B in reversed(bridges):
        if uf.same(A, B):
            ans.append(ans[-1])
        else:
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
            uf.union(A, B)
    ans.pop()
    return '\n'.join(map(str, reversed(ans)))

print(solve())