Problem p03108 (python)

Fixed submission:
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]
 
    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

    def size(self, i):
        p = self.find(i)
        return self.sizes[p]


N, M = map(int, input().split())
AB = []
B = []
for m in range(M):
    a, b = map(int, input().split())
    AB.append((a-1,b-1))

ans = []
score = N * (N-1) // 2
uf = UnionFind(N)
for a, b in AB[::-1]:
    ans.append(score)
    if not uf.same(a,b):
        score -= uf.size(a) * uf.sizes(b)
        uf.unite(a,b)    

for score in ans[::-1]:
    print(score)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n
    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parents[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj 
            else: 
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi 
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
        
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * 1
    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parents[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if self.rank[pi] < self.rank[pj]:
            self.sizes[pj] += self.sizes[pi]
            self.parents[pi] = pj 
        else: 
            self.sizes[pi] += self.sizes[pj]
            self.parents[pj] = pi 
            if self.rank[pi] == self.rank[pj]:
                self.rank[pi] += 1
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parents[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        self.sizes[pj] += self.sizes[pi]
        self.parents[pi] = pj 
        
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parent[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        self.sizes[pj] += self.sizes[pi]
        self.parents[pi] = pj 
        
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parent[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        self.sizes[pj] += self.sizes[pi]
        self.parents[pi] = pj 
        
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        self.sizes[pj] += self.sizes[pi]
        self.parents[pi] = pj 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1) # 木の高さ
        self.n = [1] * (n+1)    # グループメンバー数
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def find_n(self, x):
        return self.n[self.find(x)]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        #if self.rank[x] < self.rank[y]:
        if True:
            self.par[x] = y
            self.n[y] = self.n[x] + self.n[y]
        else:
            self.par[y] = x
            self.n[x] = self.n[x] + self.n[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y) 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.find_n(px) * uf.find_n(py)
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi == pj:
            pass
        else:
            self.sizes[pj] += self.sizes[pi]
            self.parents[pi] = pj 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi == pj:
            pass
        else:
            size = self.sizes[pi] + self.sizes[pj]
            self.sizes[pi] = size
            self.sizes[pj] = size
            self.parents[pi] = pj
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi == pj:
            pass
        else:
            size = self.sizes[i] + self.sizes[j]
            self.sizes[i] = size
            self.sizes[j] = size
            self.parents[i] = pj
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        pi = self.parents[i]
        pj = self.parents[j]
        if pi == pj:
            pass
        else:
            size = self.sizes[pi] + self.sizes[pj]
            self.sizes[pi] = size
            self.sizes[pj] = size
            self.parents[i] = pj 
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        parent_i = self.parents[i]
        parent_j = self.parents[j]
        if parent_i == parent_j:
            pass
        else:
            size = self.sizes[i] + self.sizes[j]
            self.sizes[i] = size
            self.sizes[j] = size
            self.parents[i] = parent_j 
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.sizes = [1] * n
        self.par = list(range(n))

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

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

    def size(self, x):
        return self.sizes[self.find(x)]
N, M = map(int, input().split())
comb = [int(n * (n - 1) / 2) for n in range(100000)]
bridge = list()
 
for m in range(M):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])
bridge = bridge[::-1]
u = UnionFind(N)
ls_sm = []
for a,b in bridge:
    sm =  -  comb[u.size(a)] - comb[u.size(b)]
    u.unite(a,b)
    sm += comb[u.size(a)]
    ls_sm.append(sm)
ans = 0
for sm in ls_sm[::-1]:
    if sm > 0:
        ans += sm
    print (ans)