The idea
A disjoint set union keeps elements in groups and supports two operations: find(x), the representative of x’s group, and unite(a, b), which merges two groups.
Each element points to a parent; the root of the tree is the representative. Path compression (point straight at the root after a find) and union by size (hang the smaller tree under the larger) make both operations practically O(1).
It answers “are a and b connected?” while edges are being added, drives Kruskal’s minimum spanning tree, and handles deletions when the queries are processed in reverse.
Sample problem
684. Redundant Connection ↗ Medium
A tree with n nodes had one extra edge added. Given the n edges in order, return the edge that can be removed so the rest is a tree. If several qualify, return the one that appears last.
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] output = [1,4]
Why the solution works
Add the edges one at a time. An edge is useful if it joins two parts that were separate, and redundant if its two ends were already connected: then it closes a cycle.
“Are these two nodes already connected?” while connections keep being added is exactly what a disjoint set union answers: compare the two representatives with find, and merge the groups with one assignment.
The first edge whose ends share a representative is the one that completes the cycle, and so it is the last edge of that cycle in the input.
Complexity: O(n · α(n)) time, practically linear. O(n) memory.
Watch out
- Compare
find(a)withfind(b), neverparent[a]withparent[b]. - A DSU cannot split groups. If edges are removed, read all queries first and add the edges backwards.
- Call
initbefore the first operation.