Problem p03108 (python)

Fixed submission:
import math


class UnionFind:

    def __init__(self, N: int):
        # d[i] = <parent id> if i is a child,
        #       - <size of the group> if i is a root
        self.d = [-1 for _ in range(N)]

    def root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int):
        return -self.d[self.root(x)]

    def show(self):
        m = {}
        for n in range(len(self.d)):
            r = self.root(n)

            if r not in m:
                m[r] = [n]
            else:
                m[r].append(n)

        print("root -> childs")
        print("---------------------")
        for key in m:
            print("{} -> {}".format(key, m[key]))


class Solution:

    def solve(self, N: int, M: int, bridges):

        # solve
        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer = []

        for a, b in reversed(bridges):
            answer.append(ans)

            if not uf.same(a, b):
                ans -= uf.size(a) * uf.size(b)
                uf.unite(a, b)

        answer.reverse()

        return answer


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)

Buggy submission (verdict: Runtime Error):
import math


class Solution:

    def solve(self, N: int, M: int, bridges):

        class UnionFind:

            def __init__(self, __N: int):
                self.__N = __N
                self.__par = [i for i in range(__N)]
                self.__num_map = {i: 1 for i in range(__N)}

            def root(self, x: int) -> int:
                if self.__par[x] == x:
                    return x
                else:
                    self.__par[x] = self.root(self.__par[x])
                    return self.__par[x]

            def unite(self, x: int, y: int):
                rx = self.root(x)
                ry = self.root(y)
                if rx != ry:
                    self.__par[rx] = ry
                    __num = self.__num_map[rx] + self.__num_map[ry]
                    self.__num_map[rx] = __num
                    self.__num_map[ry] = __num

            def same(self, x: int, y: int) -> bool:
                rx = self.root(x)
                ry = self.root(y)
                return rx == ry

            def num(self, x: int) -> int:
                return self.__num_map[self.root(x)]

        # solve

        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer_reversed = [0] * M

        for i in range(M-1, -1, -1):
            answer_reversed[i] = ans
            x = bridges[i][0]
            y = bridges[i][1]
            if not uf.same(x, y):
                ans -= uf.num(x) * uf.num(y)
                uf.unite(x, y)

        return answer_reversed


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)

Buggy submission (verdict: Runtime Error):
import math


class Solution:

    def solve(self, N: int, M: int, bridges):

        class UnionFind:

            def __init__(self, __N: int):
                self.__N = __N
                self.__par = [i for i in range(__N)]
                self.__num_map = {i: 1 for i in range(__N)}

            def root(self, x: int) -> int:
                if self.__par[x] == x:
                    return x
                else:
                    self.__par[x] = self.root(self.__par[x])
                    return self.__par[x]

            def unite(self, x: int, y: int):
                rx = self.root(x)
                ry = self.root(y)
                if rx != ry:
                    self.__par[rx] = ry
                    __num = self.__num_map[rx] + self.__num_map[ry]
                    self.__num_map[rx] = __num
                    self.__num_map[ry] = __num

            def same(self, x: int, y: int) -> bool:
                rx = self.root(x)
                ry = self.root(y)
                return rx == ry

            def num(self, x: int) -> int:
                return self.__num_map[self.root(x)]

        # solve

        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer_reversed = []

        for i in range(M-1, -1, -1):
            answer_reversed.append(ans)
            x = bridges[i][0]
            y = bridges[i][1]
            if not uf.same(x, y):
                ans -= uf.num(x) * uf.num(y)
                uf.unite(x, y)

        return reversed(answer_reversed)


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)

Buggy submission (verdict: Runtime Error):
import math


class Solution:

    def solve(self, N: int, M: int, bridges):

        class UnionFind:

            def __init__(self, __N: int):
                self.__N = __N
                self.__par = [i for i in range(__N)]
                self.__num_map = {i: 1 for i in range(__N)}

            def root(self, x: int) -> int:
                if self.__par[x] == x:
                    return x
                else:
                    self.__par[x] = self.root(self.__par[x])
                    return self.__par[x]

            def unite(self, x: int, y: int):
                rx = self.root(x)
                ry = self.root(y)
                if rx != ry:
                    self.__par[rx] = ry
                    __num = self.__num_map[rx] + self.__num_map[ry]
                    self.__num_map[rx] = __num
                    self.__num_map[ry] = __num

            def same(self, x: int, y: int) -> bool:
                rx = self.root(x)
                ry = self.root(y)
                return rx == ry

            def num(self, x: int) -> int:
                return self.__num_map[self.root[x]]

        # solve

        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer_reversed = []

        for i in range(M-1, -1, -1):
            answer_reversed.append(ans)
            x = bridges[i][0]
            y = bridges[i][1]
            if not uf.same(x, y):
                ans -= uf.num(x) * uf.num(y)
                uf.unite(x, y)

        return reversed(answer_reversed)


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)

Buggy submission (verdict: Runtime Error):
import math


class Solution:

    def solve(self, N: int, M: int, bridges):

        class UnionFind:

            def __init__(self, __N: int):
                self.__N = __N
                self.__par = [i for i in range(__N)]
                self.__num_map = {i: 1 for i in range(__N)}

            def root(self, x: int) -> int:
                if self.__par[x] == x:
                    return x
                else:
                    self.__par[x] = self.root(self.__par[x])
                    return self.__par[x]

            def unite(self, x: int, y: int):
                rx = self.root(x)
                ry = self.root(y)
                if rx != ry:
                    self.__par[rx] = ry
                    __num = self.__num_map[rx] + self.__num_map[ry]
                    self.__num_map[rx] = __num
                    self.__num_map[ry] = __num

            def same(self, x: int, y: int) -> bool:
                rx = self.root(x)
                ry = self.root(y)
                return rx == ry

            def num(self, x: int) -> int:
                return self.__num_map[self.__par[x]]

        # solve

        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer_reversed = []

        for i in range(M-1, -1, -1):
            answer_reversed.append(ans)
            x = bridges[i][0]
            y = bridges[i][1]
            if not uf.same(x, y):
                ans -= uf.num(x) * uf.num(y)
                uf.unite(x, y)

        return reversed(answer_reversed)


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)

Buggy submission (verdict: Runtime Error):
import math


class Solution:

    def solve(self, N: int, M: int, bridges):

        class UnionFind:

            def __init__(self, __N: int):
                self.__N = __N
                self.__par = [i for i in range(__N)]
                self.__num_map = {i: 1 for i in range(__N)}

            def root(self, x: int) -> int:
                if self.__par[x] == x:
                    return x
                else:
                    self.__par[x] = self.root(self.__par[x])
                    return self.__par[x]

            def unite(self, x: int, y: int):
                rx = self.root(x)
                ry = self.root(y)
                if rx != ry:
                    self.__par[rx] = ry
                    __num = self.__num_map[rx] + self.__num_map[ry]
                    self.__num_map[rx] = __num
                    self.__num_map[ry] = __num

            def same(self, x: int, y: int) -> bool:
                rx = self.root(x)
                ry = self.root(y)
                return rx == ry

            def num(self, x: int) -> int:
                return self.__num_map[x]

        # solve

        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer_reversed = []

        for i in range(M-1, -1, -1):
            answer_reversed.append(ans)
            x = bridges[i][0]
            y = bridges[i][1]
            if not uf.same(x, y):
                ans -= uf.num(x) * uf.num(y)
                uf.unite(bridges[i][0], bridges[i][1])

        return reversed(answer_reversed)


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)