Problem p03108 (python)

Fixed submission:
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])
    bridges = bridges[::-1]
    parent = [i for i in range(N+1)]
    count = dict()
    for i in range(N+1): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            if count[pi] > count[pj]:
                parent[pj] = pi
                df += count[pi] * count[pj]
                count[pi] += count[pj]
                del count[pj]
            else:
                parent[pi] = pj
                df += count[pi] * count[pj]
                count[pj] += count[pi]
                del count[pi]                
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges[:-1]:
        d = union(a, b)
        ans.append(ans[-1]-d)
    return ans[::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])
    bridges = bridges[::-1]
    parent = [i for i in range(N+1)]
    count = dict()
    for i in range(N+1): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
            del count[pj]
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges[:-1]:
        d = union(a, b)
        ans.append(ans[-1]-d)
    return ans[::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)

Buggy submission (verdict: Runtime Error):
import collections

class UnionFind:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.parent = [i for i in range(N+1)]
        self.count = [1 for _ in range(N+1)]

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi != pj:
            self.parent[pj] = pi
            self.count[pi] += self.count[pj]

    def isConnected(self, i, j):
        return self.find(i) == self.find(j)

def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    UF = UnionFind(N, M)

    ans = [N*(N-1)//2]
    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        if UF.isConnected(a, b):
            ans.append(ans[-1])
        else:
            ans.append(ans[-1]- UF.count[UF.find(a)]*UF.count[UF.find(b)])
            UF.union(a, b)
    return ans

if __name__ == '__main__':
    output = main()
    for i in range(len(output)-1, -1, -1):
        print(output[i])

Buggy submission (verdict: Runtime Error):
import collections

class UnionFind:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.parent = [i for i in range(N+1)]
        self.count = [1 for _ in range(N+1)]

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        df = 0
        if pi != pj:
            self.parent[pj] = pi
            df += self.count[pi] * self.count[pj]
            self.count[pi] += self.count[pj]
        return df

def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    UF = UnionFind(N, M)

    ans = [N*(N-1)//2]
    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        d = UF.union(a, b)
        ans.append(ans[-1]-d)
    return ans

if __name__ == '__main__':
    output = main()
    for i in range(len(output)-1, -1, -1):
        print(output[i])

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    parent = [i for i in range(N+1)]
    count = [1 for _ in range(N+1)]

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
        return df

    ans = [N*(N-1)//2]
    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        d = union(a, b)
        ans.append(ans[-1]-d)
    return ans

if __name__ == '__main__':
    output = main()
    for i in range(len(output)-1, -1, -1):
        print(output[i])

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])
    bridges = bridges[::-1]
    parent = [i for i in range(N+1)]
    count = dict()
    for i in range(N+1): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
            del count[pj]
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges[:-1]:
        d = union(a, b)
        v = ans[-1]
        ans.append(v-d)
    return ans[::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])
    bridges = bridges[::-1]
    parent = [i for i in range(N+1)]
    count = dict()
    for i in range(N+1): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
            del count[pj]
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges[:-1]:
        d = union(a, b)
        ans.append(ans[-1] - d)
    return ans[::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a-1, b-1])
    bridges = bridges[::-1]
    parent = [i for i in range(N)]
    count = dict()
    for i in range(N): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
            del count[pj]
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges[:-1]:
        d = union(a, b)
        ans.append(ans[-1] - d)
    return ans[::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a-1, b-1])
    bridges = bridges[::-1]
    parent = [i for i in range(N)]
    count = collections.defaultdict(int)
    for i in range(N): count[i] = 1

    def find(i, parent):
        if parent[i] != i:
            parent[i] = find(parent[i], parent)
        return parent[i]

    def union(i, j, parent, count):
        pi, pj = find(i, parent), find(j, parent)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges:
        d = union(a, b, parent, count)
        ans.append(ans[-1] - d)
    return ans[:-1][::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(str(v))

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a-1, b-1])
    bridges = bridges[::-1]
    parent = [i for i in range(N)]
    count = collections.defaultdict(int)
    for i in range(N): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
        return df

    ans = []
    if N % 2 == 0:
        ans.append((N//2)*(N-1))
    else:
        ans.append(N*((N-1)//2))
    for a, b in bridges:
        d = union(a, b)
        ans.append(ans[-1] - d)
    return ans[:-1][::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(str(v))

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a-1, b-1])
    bridges = bridges[::-1]
    parent = [i for i in range(N)]
    count = collections.defaultdict(int)
    for i in range(N): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
        return df

    if N % 2 == 0:
        ans.append((N//2)*(N-1))
    else:
        ans.append(N*((N-1)//2))
    for a, b in bridges:
        d = union(a, b)
        ans.append(ans[-1] - d)
    return ans[:-1][::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(str(v))

Buggy submission (verdict: Runtime Error):
import collections
def main():
    N, M = map(int, input().split())
    bridges = []
    for _ in range(M):
        a, b = map(int, input().split())
        bridges.append([a-1, b-1])
    bridges = bridges[::-1]
    parent = [i for i in range(N)]
    count = collections.defaultdict(int)
    for i in range(N): count[i] = 1

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        df = 0
        if pi != pj:
            parent[pj] = pi
            df += count[pi] * count[pj]
            count[pi] += count[pj]
        return df

    ans = [N*(N-1)//2]
    for a, b in bridges:
        d = union(a, b)
        ans.append(ans[-1] - d)
    return ans[:-1][::-1]

if __name__ == '__main__':
    output = main()
    for v in output:
        print(v)