[Python] UnionFind ABC177D

ABC177D

There are various implementations of UnionFind, but in this question, it is very easy to solve the implementation that holds the number of nodes in the parents array. The number of nodes is held as follows.

-When it is a child, it stores the parent node number. When it is a root, it stores the number of nodes as a negative number. -When the number is negative, it is the root, and its absolute value represents the number of nodes in the tree.

`Sample code`


import sys

#UnionFindTree class definition
class UnionFind():
    #Class constructor
    #self is the instance itself
    def __init__(self, n):
        #Parent node-Initialize to 1
        self.parents = [-1] * n

    #Find the root
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #Merge x and y trees
    def union(self, x, y):
        #Root search
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#Creating a Union Find instance
uf = UnionFind(N)
for a, b in info:
    #Adjust the index, a,b join trees
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)