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)
Recommended Posts