Problem p03108 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

uf = UnionFind(N + 1)
group_size = dict([(i, 1) for i in range(N+1)])
cur = N * (N-1) // 2
ans = [cur]
for a, b in reversed(AB):
    x = uf.find(a)
    y = uf.find(b)
    if x != y:
        cur -= group_size[y] * group_size[x]
        uf.union(a, b)
        group_size[y] += group_size[x]
        del group_size[x]
    ans.append(cur)

for n in reversed(ans[:-1]):
    print(n)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

N, M = map(int, input().split())

uf = UnionFind(N + 1)
group_size = dict([(i, 1) for i in range(N+1)])
cur = N * (N-1) // 2
ans = [cur]
for _ in range(M-1):
    a, b = map(int, input().split())
    x = uf.find(a)
    y = uf.find(b)
    if x != y:
        cur -= group_size[y] * group_size[x]
        uf.union(a, b)
        group_size[y] += group_size[x]
        del group_size[x]
    ans.append(cur)

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

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def C(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )
    def H(self, n, r):
        return self.C(n - 1 + r, r)

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

uf = UnionFind(N + 1)
comb = Combination()

group_size = dict([(i, 1) for i in range(N+1)])
cur = comb.C(N, 2)
ans = [cur]
for a, b in reversed(AB):
    x = uf.find(a)
    y = uf.find(b)
    if x != y:
        uf.union(a, b)
        cur -= group_size[y] * group_size[x]
        group_size[y] += group_size[x]
        del group_size[x]

    ans.append(cur)
for n in reversed(ans[:-1]):
    print(int(n))

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def C(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )
    def H(self, n, r):
        return self.C(n - 1 + r, r)

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

uf = UnionFind(N + 1)
comb = Combination()

group_size = dict([(i, 1) for i in range(1, N+1)])
cur = comb.C(N, 2)
ans = [cur]
for a, b in reversed(AB):
    x = uf.find(a)
    y = uf.find(b)
    if x != y:
        uf.union(a, b)
        cur -= group_size[y] * group_size[x]
        group_size[y] += group_size[x]
        del group_size[x]

    ans.append(cur)
for n in reversed(ans[:-1]):
    print(int(n))