Problem p03108 (python)

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

bridge.reverse()
bridge = bridge[:-1]

inconvenience = N * (N - 1) // 2
inconvenience_history = [inconvenience]


class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)
        self._number = [1] * (N + 1)

    def root(self, i):
        if self.par[i] == i:
            return i
        self.par[i] = self.root(self.par[i])
        return self.par[i]

    def tree_rank(self, i):
        return self.rank[self.root(i)]

    def number(self, i):
        return self._number[self.root(i)]

    def union(self, i, j):
        _root_i = self.root(i)
        _root_j = self.root(j)
        if _root_i == _root_j:
            return
        else:
            if self.tree_rank(i) < self.tree_rank(j):
                self.par[_root_i] = _root_j
                self._number[_root_j] += self._number[_root_i]
            else:
                self.par[_root_j] = _root_i
                self._number[_root_i] += self._number[_root_j]
                if self.tree_rank(i) == self.tree_rank(j):
                    self.rank[_root_i] += 1


islands = UnionFind(N)

for A_i, B_i in bridge:

    root_A = islands.root(A_i)
    root_B = islands.root(B_i)

    if root_A == root_B:
        inconvenience_history.append(inconvenience)
        continue
    else:
        improvement = islands.number(A_i) * islands.number(B_i)
        islands.union(A_i, B_i)

        inconvenience -= improvement
        if inconvenience == 0:
            inconvenience_history += [0] * (M - len(inconvenience_history))
            break
        inconvenience_history.append(inconvenience)

print(*inconvenience_history[::-1], sep='\n')

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

bridge.reverse()
bridge = bridge[:-1]

inconvenience = N * (N - 1) // 2
inconvenience_history = [inconvenience]


class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]
        self._number = [1] * (N + 1)

    def root(self, i):
        if self.par[i] == i:
            return i
        self.par[i] = self.root(self.par[i])
        return self.par[i]

    def number(self, i):
        return self._number[self.root(i)]

    def union(self, i, j):
        _root_i = self.root(i)
        _root_j = self.root(j)
        if _root_i == _root_j:
            return
        else:
			self.par[_root_j] = _root_i
            self._number[_root_i] += self._number[_root_j]


islands = UnionFind(N)

for A_i, B_i in bridge:

    root_A = islands.root(A_i)
    root_B = islands.root(B_i)

    if root_A == root_B:
        inconvenience_history.append(inconvenience)
        continue
    else:
        improvement = islands.number(A_i) * islands.number(B_i)
        islands.union(A_i, B_i)

        inconvenience -= improvement
        if inconvenience == 0:
            inconvenience_history += [0] * (M - len(inconvenience_history))
            break
        inconvenience_history.append(inconvenience)

print(*inconvenience_history[::-1], sep='\n')

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

bridge.reverse()
bridge = bridge[:-1]

inconvenience = N * (N - 1) // 2
inconvenience_history = [inconvenience]


class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)
        self._number = [1] * (N + 1)

    def root(self, i):
        if self.par[i] == i:
            return i
        self.par[i] = self.root(self.par[i])
        return self.par[i]

    def tree_rank(self, i):
        return self.rank[self.root(i)]

    def number(self, i):
        return self._number[self.root(i)]

    def union(self, i, j):
        _root_i = self.root(i)
        _root_j = self.root(j)
        if _root_i == _root_j:
            return
        else:
            if self.tree_rank(i) < self.tree_rank(j):
                self.par[_root_i] = _root_j
                self._number[_root_j] += self._number[_root_i]
            else:
                self.par[_root_j] = _root_i
                self._number[_root_i] += self._number[_root_j]
                if self.tree_rank(i) == self.tree_rank(j):
                    self.rank[_root_i] += 1


islands = UnionFind(N)

for A_i, B_i in bridge:

    islands.pri()

    root_A = islands.root(A_i)
    root_B = islands.root(B_i)

    if root_A == root_B:
        inconvenience_history.append(inconvenience)
        continue
    else:
        improvement = islands.number(A_i) * islands.number(B_i)
        islands.union(A_i, B_i)

        inconvenience -= improvement
        if inconvenience == 0:
            inconvenience_history += [0] * (M - len(inconvenience_history))
            break
        inconvenience_history.append(inconvenience)

print(*inconvenience_history[::-1], sep='\n')

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

bridge.reverse()
bridge = bridge[:-1]

islands_group = []
inconvenience = N * (N - 1) // 2
inconvenience_history = [inconvenience]

for A_i, B_i in bridge:

    islands_of_A = set()
    islands_of_B = set()

    for j, islands in enumerate(islands_group):
        if A_i in islands: islands_of_A = islands_group.pop(j)
        if B_i in islands: islands_of_B = islands_group.pop(j)

        if islands_of_A and islands_of_B:
            if islands_of_A == islands_of_B:
                improvement = 0
            else:
                improvement = len(islands_of_A) * len(islands_of_B)
                islands_group.append(islands_of_A | islands_of_B)
            break
    else:
        if not islands_of_A and not islands_of_B:
            improvement = 1
            islands_group.append({A_i, B_i})
        else:
            if islands_of_A:
                improvement = len(islands_of_A)
                islands_group.append(islands_of_A | {B_i})
            else:
                improvement = len(islands_of_B)
                islands_group.append(islands_of_B | {A_i})

    inconvenience -= improvement
    if inconvenience == 0:
        inconvenience_history += [0] * (M - len(inconvenience_history))
        break
    inconvenience_history.append(inconvenience)

print(*inconvenience_history[::-1], sep='\n')