Trace Union and Find on a Parent Array

Find both roots first, then point one root at the other.

Tracing union-find means keeping its parent array on paper and updating it one union at a time. This card covers tracing four unions on six items to the final array, and reading the groups back from that array, the skill every union-find problem rests on.

In union-find each item holds a parent, another item or itself, and an item that is its own parent is a root, the representative of its group. find(x) follows parents from x to the root. union(a, b), as traced here, finds both roots and sets the parent of a's root to b's root, with no optimisations, so every step can be checked by hand.

The input is six items, 0 to 5, so the array starts as 0 1 2 3 4 5, and the unions are union(0, 1), union(1, 2), union(3, 4) and union(0, 4). Work out the final array before reading the trace.

Predict: what is the parent array after the four unions?

1 2 4 4 4 5. In the last union, find(0) climbs from 0 to 1 to 2, so it is the parent of 2 that changes, to 4, and the parent of 0 stays 1.

The trace shows the array after each union. The root-a marker sits on the root of the first argument, whose parent changes, and root-b on the root it is linked under.

The parent array after each union

InputElements 0 to 5; union(0, 1), union(1, 2), union(3, 4), union(0, 4), each setting the parent of a's root to b's root

Start
1. 0
2. 1
3. 2
4. 3
5. 4
6. 5
Every element is its own root, so each parent is the element itself.
union(0,1)
1. 1root-a
2. 1root-b
3. 2
4. 3
5. 4
6. 5
0 and 1 are both roots, so the parent of 0 becomes 1.
union(1,2)
1. 1
2. 2root-a
3. 2root-b
4. 3
5. 4
6. 5
find(1) is 1 and find(2) is 2, so the parent of 1 becomes 2, and 0 reaches 2 through 1.
union(3,4)
1. 1
2. 2
3. 2
4. 4root-a
5. 4root-b
6. 5
A second group starts: 3 and 4 are roots, so the parent of 3 becomes 4.
union(0,4)
1. 1
2. 2
3. 4root-a
4. 4
5. 4root-b
6. 5
find(0) climbs 0, 1, 2 to root 2 and find(4) is 4, so the parent of root 2 becomes 4, not the parent of 0.

ResultParent array 1 2 4 4 4 5: elements 0 to 4 share root 4, and 5 is alone

Every union changed exactly one cell, and it was always a root's cell. In the last frame, union(0, 4) changed cell 2, not cell 0, because 2 was the root that find(0) reached.

To read the groups back, run find on every item. 0 climbs 0, 1, 2, 4; 1 climbs 1, 2, 4; 2 and 3 each reach 4 in one step; 4 is its own root, and so is 5. That gives two groups, {0, 1, 2, 3, 4} with root 4 and {5} on its own, and the run printed the same roots. A root is a cell whose value equals its index, so counting those cells, here 4 and 5, counts the groups without running find at all.

The order of the arguments decides which root ends up on top, but not which items share a group. union(4, 0) in place of the last union would have set the parent of 4 to 2 instead, and left 0 to 4 in one group all the same.

← → move through sections and cards