Union Find is a data structure to
- find whether two elements in the same group (Find)
- merge two groups of elements (Union)
Here is an example story to help you understand Union Find.
A, B, C three people work for M company. We assign them each a parent pointer to M.
D, E, F, G four people work for L company. We assign them each a parent pointer to L.
Parent pointer tells which group a person belongs to. A’s parent is M. F’s parent is L. Suppose A meets F, they know they are not in the same company. If D comes, F knows D is a colleague.
Suppose one day M acquired L. We simply let M be L’s parent. Then D, E, F, G all join M.
Union Find Basic Operations
1. Initialization
We can simply initialize Union Find by assigning each element’s parent to themselves.
int[] parent; public UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } }
2. Find
To find which group the element belongs to.
private int find(int x) { if (parent[x] == x) { return x; } return parent[x] = find(parent[x]); }
Time Complexity: O(1).
3. Union
Merge two groups into one group.
public void union(int a, int b) { int rootA = find(a); int rootB = find(b); if (rootA != rootB) { parent[rootA] = rootB; } }
Time Complexity: O(1).
Thanks for the article and explanation.