Union-find

Union-find answers one question — are these two things in the same group? — and answers it in effectively constant time, for a problem that looks like it should need a graph traversal.

It is small enough to write from memory and it is the right answer surprisingly often.

#The structure

Every element points at a parent. Follow parents until you reach one that points at itself: that is the group's representative. Two elements are in the same group when they have the same representative.

int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;      // everyone is their own group
 
int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}
 
void union(int a, int b) {
    parent[find(a)] = find(b);                   // point one representative at the other
}

That is a complete implementation, and it has one problem: the trees can degenerate into a chain, and then find is O(n).

#Path compression, measured

A deliberate worst case — a chain of a hundred thousand — then find on every element:

###   without path compression   3069 ms
###   with path compression         1 ms

Three thousand times, and the change is one line inside the loop:

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];    // point at grandparent on the way past
        x = parent[x];
    }
    return x;
}

Every find flattens the path it walked, so the work is done once and every later query is short. This is the same idea as memoisation in the previous lesson: pay once, and leave the answer where you will look next time.

The second optimisation is union by rank (or size): when joining two trees, hang the shorter under the taller, so the result stays shallow. With both, the amortised cost is the inverse Ackermann function — a value below 5 for any n you will ever have, which is why union-find is described as "effectively constant".

#What it is for

The pattern is: things get merged into groups, and you need to ask about membership as you go.

• Cycle detection while building. Adding an edge between two vertices already in the same group creates a cycle. This is Kruskal's minimum spanning tree, and it is the classic use.
• Connected components. Union every edge; count distinct representatives.
• "Are these two accounts the same person?" Merge on each piece of evidence, query at any point.
• Grid problems — islands, percolation — where adjacent cells merge.
• Detecting a cycle in a dependency graph as it is constructed, rather than after.

And what it is not for, which is the part that decides whether to reach for it:

• It cannot un-merge. There is no split. If groups can come apart, this is the wrong structure and you need something that recomputes.
• It does not give you the path, only whether one exists. "Are A and B connected" — yes. "How are they connected" — use BFS.
• It has no order. The representative is an arbitrary member, not a smallest or a first.

#Against the alternative

For "are these connected", the obvious alternative is DFS or BFS from one of them.

So the decision is: many queries, or a graph that grows. A single connectivity question on a graph you already have is a traversal. Ten thousand questions, or edges arriving one at a time, is union-find.