Buggy python submission (verdict: Time Limit Exceeded):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

    def size(self, x):
        count = 0
        # 親の繋ぎ変えがまだかもしれないので, find 経由で
        parent = self.find(x)
        for i in range(self.n):
            if self.find(i) == parent:
                count += 1

        return count

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

uf = UnionFind(N)

i = M-1
ans = [0] * M
x = (N*(N-1)//2)
while i >= 0:
    ans[i] = x

    if not uf.same(A[i], B[i]):
        x -= uf.size(A[i])*uf.size(B[i])

    uf.unite(A[i], B[i])
    i -= 1


for i in ans:
    print(i)

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                self.size[x] += self.size[y]
            else:
                self.size[x] += self.size[y]

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

    def get_size(self, x):
        root = self.find(x)
        return self.size[root]



N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

uf = UnionFind(N)

i = M-1
ans = [0] * M
x = (N*(N-1)//2)
while i >= 0:
    ans[i] = x

    if not uf.same(A[i], B[i]):
        x -= uf.get_size(A[i]) * uf.get_size(B[i])

    uf.unite(A[i], B[i])
    i -= 1


for i in ans:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

def count(uf):
    count = 0
    for i in range(N):
        for j in range(i, N):
            if not uf.same(i, j):
                count += 1
    return count

uf = UnionFind(N)

i = M-1
ans = [0] * M
while i >= 0:
    ans[i] = count(uf)
    uf.unite(A[i], B[i])
    i -= 1

for i in ans:
    print(i)


Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                self.size[x] += self.size[y]
            else:
                self.size[x] += self.size[y]

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

    def get_size(self, x):
        root = self.find(x)
        return self.size[root]



N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

uf = UnionFind(N)

i = M-1
ans = [0] * M
x = (N*(N-1)//2)
while i >= 0:
    ans[i] = x

    if not uf.same(A[i], B[i]):
        x -= uf.get_size(A[i]) * uf.get_size(B[i])

    uf.unite(A[i], B[i])
    i -= 1


for i in ans:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

def count(uf):
    count = 0
    for i in range(N):
        for j in range(i, N):
            if not uf.same(i, j):
                count += 1
    return count

uf = UnionFind(N)

i = M-1
ans = [0] * M
while i >= 0:
    ans[i] = count(uf)
    uf.unite(A[i], B[i])
    i -= 1

for i in ans:
    print(i)


Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                self.size[x] += self.size[y]
            else:
                self.size[x] += self.size[y]

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

    def get_size(self, x):
        root = self.find(x)
        return self.size[root]



N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

uf = UnionFind(N)

i = M-1
ans = [0] * M
x = (N*(N-1)//2)
while i >= 0:
    ans[i] = x

    if not uf.same(A[i], B[i]):
        x -= uf.get_size(A[i]) * uf.get_size(B[i])

    uf.unite(A[i], B[i])
    i -= 1


for i in ans:
    print(i)