How do you implement a union find disjoint set structure?
You keep a list of parents and a list of sizes. Every node starts as its own group, and joining two groups means making one the parent of the other.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, node):
while node != self.parent[node]:
self.parent[node] = self.parent[self.parent[node]]
node = self.parent[node]
return node
def union(self, first, second):
root_first = self.find(first)
root_second = self.find(second)
if root_first == root_second:
return False
if self.rank[root_first] < self.rank[root_second]:
root_first, root_second = root_second, root_first
self.parent[root_second] = root_first
if self.rank[root_first] == self.rank[root_second]:
self.rank[root_first] += 1
return True
So how does it work? The parent list says which group each node belongs to. The root of a group is the node that is its own parent. And the find method walks up the parents until it reaches the root, and that root is the name of the group.
And the union method joins two groups. It finds the root of each one, and if they are the same then they are already in the same group and nothing happens. Otherwise one root is made the parent of the other.
the groups the parent list
0, 1, 2, 3 [0, 1, 2, 3]
union 0 and 1 [0, 0, 2, 3]
union 1 and 2 [0, 0, 0, 3]
find 2 gives 0
And the two tricks are what make it fast. The first one is path compression, which is the line self.parent[node] = self.parent[self.parent[node]]. When you walk up the parents you point each node at its grandparent, so the trees get flatter and flatter and the walks get shorter.
The second one is union by rank, which is the size list. When you join two groups you make the root of the bigger one the parent of the root of the smaller one. That keeps the trees shallow, because a node never has more than log n ancestors.
And the complexity is almost constant for both operations. The find and the union take O of alpha of n, which is almost O of 1, and alpha grows so slowly that for any realistic number of nodes it is under five.
So the rule to remember is this. Path compression and union by rank are the two things that make it fast.
The last question in this topic shows how to count components with it.