Problem p03108 (python)

Fixed submission:
#UnionFindクラス
class UnionFind:
    def __init__(self,n):
        self.par =  [i for i in range(n)]
        self.rank = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # xとyの根を結合させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        self.rank[x] += self.rank[y]
        self.par[y] = x

    # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれる木の要素数を返す
    def size(self, x):
        return self.rank[self.find(x)]
    
n,m = map(int,input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
uf = UnionFind(n)
accm = []
for ai,bi in reversed(ab):
    if uf.is_same(ai,bi):
        accm.append(0)
    else:
        accm.append(uf.size(ai)*uf.size(bi))
    uf.union(ai,bi)

accm = accm[::-1]
for i in range(1,len(accm)):
    accm[i] += accm[i-1]
for a in accm:
    print(a)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] # 親の番号
        self.size = [1]*n
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        # self.size[x] = 0
        
    def get_size(self, x:int)->int:
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = list(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)
for ai,bi in reversed(ab):
    if uf.is_same(ai,bi):
        ans.append(0)
    else:
        ans.append(uf.get_size(ai)*uf.get_size(bi))
    uf.unite(ai,bi)
print(0)
ans = ans[::-1]
for i in range(1,len(ans)):
    ans[i] += ans[i-1]
    print(ans[i])

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] # 親の番号
        self.size = [1]*n
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        # self.size[x] = 0
        
    def get_size(self, x:int)->int:
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = list(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)
for ai,bi in reversed(ab):
    ans.append(nex)
    if uf.is_same(ai,bi):
        nex = nex
    else:
        nex = nex - uf.get_size(ai)*uf.get_size(bi)
    uf.unite(ai,bi)
for a in reversed(ans):
    print(a)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] # 親の番号
        self.size = [1]*n
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        # self.size[x] = 0
        
    def get_size(self, x:int)->int:
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = list(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)
for ai,bi in reversed(ab):
    ans.append(nex)
    if uf.is_same(ai,bi):
        nex = nex
    else:
        nex = nex - uf.get_size(ai)*uf.get_size(bi)
        uf.unite(ai,bi)
for a in reversed(ans):
    print(a)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] # 親の番号
        self.size = [1]*n
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        self.size[x] = 0
        
    def get_size(self, x:int)->int:
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)
for ai,bi in reversed(ab):
    ans.append(nex)
    if uf.is_same(ai,bi):
        nex = nex
    else:
        nex = nex - uf.get_size(ai)*uf.get_size(bi)
        uf.unite(ai,bi)
for a in reversed(ans):
    print(a)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    """size(int)を指定
    root(x:int)->int:      根を求める
    unite(x,y:int):        要素をグループにまとめる 
    isSame(x,y:int)->bool: 要素同士が同じグループか判定する
    """
    # 分離はできない
    # 始め各要素は別々のグループ  
    def __init__(self,n):
        self.par = [-1]*n # 親の番号
        self.size = [1]*n
        for i in range(n):
            self.par[i] = i  # はじめ すべての頂点が根
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        self.size[x] = 0
        
    def getsize(self, x:int):
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)

for ai,bi in reversed(ab):
    ans.append(nex)
    if nex==0: continue
    sa = uf.getsize(ai)
    sb = uf.getsize(bi)
    nex = ans[-1] + comb2(sa) + comb2(sb)
    uf.unite(ai,bi)
    nex -= comb2(uf.getsize(ai))
    

for a in reversed(ans):
    print(a)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    """size(int)を指定
    root(x:int)->int:      根を求める
    unite(x,y:int):        要素をグループにまとめる 
    isSame(x,y:int)->bool: 要素同士が同じグループか判定する
    """
    # 分離はできない
    # 始め各要素は別々のグループ  
    def __init__(self,n):
        self.par = [-1]*n # 親の番号
        self.size = [1]*n
        for i in range(n):
            self.par[i] = i  # はじめ すべての頂点が根
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        self.size[x] = 0
        
    def getsize(self, x:int):
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)

for ai,bi in reversed(ab):
    ans.append(nex)
    sa = uf.getsize(ai)
    sb = uf.getsize(bi)
    nex = ans[-1] + comb2(sa) + comb2(sb)
    uf.unite(ai,bi)
    nex -= comb2(uf.getsize(ai))
    

for a in reversed(ans):
    print(a)