Linking the Nodes Instead of Their Roots

A union that sets the parent of the item it was given, rather than the parent of that item's root, looks correct and breaks groups apart. This card covers what that mistake does to a parent array, why it loses items from their group, and the one-line fix.

In union-find each item stores a parent, and an item that is its own parent is the root of its group. find(x) follows parents to the root, and two items share a group when they reach the same root. The correct union(a, b) sets the parent of find(a) to find(b).

The tempting version is shorter: parent[a] = b. It gives the right answer whenever a is already a root, which is true of the first few unions in any small test, so it passes them. A run applied the same three unions, union(0, 1), union(1, 2) and union(0, 3), to six items both ways.

def find(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x


def union_nodes(parent, a, b):
    parent[a] = b


def union_roots(parent, a, b):
    parent[find(parent, a)] = find(parent, b)


unions = [(0, 1), (1, 2), (0, 3)]
for label, union in (("linking the nodes", union_nodes), ("linking the roots", union_roots)):
    parent = list(range(6))
    for a, b in unions:
        union(parent, a, b)
    groups = {}
    for element in range(6):
        groups.setdefault(find(parent, element), []).append(element)
    print(f"{label}: {' '.join(map(str, parent))}")
    print(f"  groups: {list(groups.values())}")
    print(f"  1 and 3 in one group: {find(parent, 1) == find(parent, 3)}")

linking the nodes: 3 2 2 3 4 5
  groups: [[0, 3], [1, 2], [4], [5]]
  1 and 3 in one group: False
linking the roots: 1 2 3 3 4 5
  groups: [[0, 1, 2, 3], [4], [5]]
  1 and 3 in one group: True

The first two unions agree, because 0 and 1 are roots when they are named, but the third does not. By then 0 already has a parent, 1, so parent[0] = 3 cuts 0 loose from 1 and 2 and hangs it under 3. The group {0, 1, 2} that existed a moment earlier is split, and the array reads 3 2 2 3 4 5. Asked whether 1 and 3 share a group, it answers no, although the three unions joined them.

The correct version climbs from 0 to its root, 2, and sets the parent of 2 to 3, so the whole group moves at once: 1 2 3 3 4 5, one group holding 0 to 3.

The cause is that a parent is the only link an item has to its group. Overwriting the parent of an item that is not a root throws that link away, so the item and everything below it leave, and everything above it stays behind. The fix is to call find on both arguments and link roots, never nodes.

To catch the bug, test a union whose first argument is not a root, then check that every item of both groups reports the same root afterwards. A test that only joins items still on their own cannot catch it.