Union-Find uses a parent array. If parent[i] == i, then is a root. Otherwise, parent[i] points to 's parent.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
Initially, every node is its own root (a forest of single-node trees).
To find the root of a node, follow parent pointers:
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
To check if two nodes are connected:
def connected(self, x, y):
return self.find(x) == self.find(y)
Same root means same component.