Problem p03108 (python)

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

ans = 0

class UFT:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1] * N
    def add_size(self, dst, size):
        dst_tmp = self.parent[dst]
        self.size[dst] += size
        if dst_tmp != dst:
            self.add_size(dst_tmp, size)
        #
        return
    def connect(self, src, dst):
        dst_prev = self.parent[src]
        size_src = self.size[src]
        if dst_prev != src:
            self.add_size(dst_prev, -size_src)
        if dst != src:
            self.add_size(dst, size_src)
        self.parent[src] = dst
        return
    def root(self, src):
        dst = self.parent[src]
        if src == dst:
            ret = src
        else:
            src_root = self.root(dst)
            ret = src_root
        #
        return ret
    def unite(self, src, dst):
        src_root = self.root(src)
        dst_root = self.root(dst)
        if src != src_root:
            self.unite(self.parent[src], dst_root)
        self.connect(src, dst_root)
        #
        return

ans = []
ans_tmp = N * (N - 1) // 2
tree = UFT(N)
for i_inv, (Ai, Bi) in enumerate(AB[::-1]):
    i = N - 1 - i_inv
    # print("#", tree.parent, tree.size)
    ans.append(ans_tmp)
    A_root = tree.root(Ai - 1)
    B_root = tree.root(Bi - 1)
    if A_root != B_root:
        ans_tmp -= (tree.size[A_root] * tree.size[B_root])
    if A_root < B_root:
        tree.unite(Ai - 1, Bi - 1)
    else:
        tree.unite(Bi - 1, Ai - 1)
        
# print("#", tree.parent, tree.size)
for ansi in ans[::-1]:
    print(ansi)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

class UFT:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1] * N
    def add_size(self, dst, size):
        dst_tmp = self.parent[dst]
        self.size[dst] += size
        if dst_tmp != dst:
            self.add_size(dst_tmp, size)
        #
        return
    def connect(self, src, dst):
        dst_prev = self.parent[src]
        size_src = self.size[src]
        if dst_prev != src:
            self.add_size(dst_prev, -size_src)
        if dst != src:
            self.add_size(dst, size_src)
        self.parent[src] = dst
        return
    def root(self, src):
        dst = self.parent[src]
        if src == dst:
            ret = src
        else:
            src_root = self.root(dst)
            ret = src_root
        #
        return ret
    def unite(self, src, dst):
        src_root = self.root(src)
        dst_root = self.root(dst)
        if self.size[src_root] < self.size[dst_root]:
            tmp = (src, src_root)
            src, src_root = (dst, dst_root)
            dst, dst_root = tmp
        #
        if src != src_root:
            self.unite(self.parent[src], dst_root)
        self.connect(src, dst_root)
        #
        return

ans = []
ans_tmp = N * (N - 1) // 2
tree = UFT(N)
for i_inv, (Ai, Bi) in enumerate(AB[::-1]):
    i = N - 1 - i_inv
    # print("#", tree.parent, tree.size)
    ans.append(ans_tmp)
    A_root = tree.root(Ai - 1)
    B_root = tree.root(Bi - 1)
    if A_root != B_root:
        ans_tmp -= (tree.size[A_root] * tree.size[B_root])
    tree.unite(Ai - 1, Bi - 1)
            
# print("#", tree.parent, tree.size)
for ansi in ans[::-1]:
    print(ansi)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

class UFT:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1] * N
    def add_size(self, dst, size):
        dst_tmp = self.parent[dst]
        self.size[dst] += size
        if dst_tmp != dst:
            self.add_size(dst_tmp, size)
        #
        return
    def connect(self, src, dst):
        dst_prev = self.parent[src]
        size_src = self.size[src]
        if dst_prev != src:
            self.add_size(dst_prev, -size_src)
        if dst != src:
            self.add_size(dst, size_src)
        self.parent[src] = dst
        return
    def root(self, src):
        dst = self.parent[src]
        if src == dst:
            ret = src
        else:
            src_root = self.root(dst)
            ret = src_root
        #
        return ret
    def unite(self, src, dst):
        src_root = self.root(src)
        dst_root = self.root(dst)
        if self.size[src_root] < self.size[dst_root]:
            self.unite(dst, src)
            return
        #
        if src != src_root:
            self.unite(self.parent[src], dst_root)
        self.connect(src, dst_root)
        #
        return

ans = []
ans_tmp = N * (N - 1) // 2
tree = UFT(N)
for i_inv, (Ai, Bi) in enumerate(AB[::-1]):
    i = N - 1 - i_inv
    # print("#", tree.parent, tree.size)
    ans.append(ans_tmp)
    A_root = tree.root(Ai - 1)
    B_root = tree.root(Bi - 1)
    if A_root != B_root:
        ans_tmp -= (tree.size[A_root] * tree.size[B_root])
    tree.unite(Ai - 1, Bi - 1)
            
# print("#", tree.parent, tree.size)
for ansi in ans[::-1]:
    print(ansi)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

ans = 0

class UFT:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1] * N
    def add_size(self, dst, size):
        dst_tmp = self.parent[dst]
        self.size[dst] += size
        if dst_tmp != dst:
            self.add_size(dst_tmp, size)
    def connect(self, src, dst):
        dst_prev = self.parent[src]
        size_src = self.size[src]
        if dst_prev != src:
            self.add_size(dst_prev, -size_src)
        if dst != src:
            self.add_size(dst, size_src)
        self.parent[src] = dst
        return
    def root(self, src):
        dst = self.parent[src]
        if src == dst:
            ret = src
        else:
            src_root = self.root(dst)
            ret = src_root
        #
        return ret
    def unite(self, src, dst):
        src_root = self.root(src)
        dst_root = self.root(dst)
        if src != src_root:
            self.unite(self.parent[src], dst_root)
        self.connect(src, dst_root)
        #
        return

ans = []
ans_tmp = N * (N - 1) // 2
tree = UFT(N)
for i_inv, (Ai, Bi) in enumerate(AB[::-1]):
    i = N - 1 - i_inv
    # print("#", tree.parent, tree.size)
    ans.append(ans_tmp)
    A_root = tree.root(Ai - 1)
    B_root = tree.root(Bi - 1)
    if A_root != B_root:
        ans_tmp -= (tree.size[A_root] * tree.size[B_root])
    tree.unite(Ai - 1, Bi - 1)
    
# print("#", tree.parent, tree.size)
for ansi in ans[::-1]:
    print(ansi)