Merging means one leader follows another

To merge the groups of two people, find each one's leader, then make one leader point to the other. That's it. Every member of both groups now leads back to the same leader, so they're all one group.

If both people already have the same leader, they're in the same group and there's nothing to do.

Merge: point one leader at the other.

Compare leaders: not the people they point to directly.

Merge everything, then answer

Process every merge in order. Then, to answer "are these two in the same group?", find each person's leader and compare. Step through the picture: after 0 joins 1 and 1 joins 2, following the arrows from 0 leads to 2, and so does 2 itself. Same leader, same group.

Person 3 was never merged with them, so 3 is still its own leader.

Same group? find both leaders and compare.

In code

parent = list(range(n))
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x
for a, b in edges:
    parent[find(a)] = find(b)
return find(query[0]) == find(query[1])

5 people, merged 0–1, 1–2, 3–4 · each arrow points towards the leader

parent: [0, 1, 2, 3, 4]

Everyone starts on their own, pointing at themselves, so there are no arrows yet. Each person is their own leader.

Move 1 of 5