Friend Groups with Union-Find
Hard · Algorithms
Union-find (disjoint set union) tracks which items belong to the same group. Every item points to a parent; the item at the top of the chain is the group leader.
- find(x): follow parents up to the leader (path compression: point nodes straight at the leader on the way)
- union(a, b): find both leaders and, if different, attach one to the other
There are n people numbered 0 to n - 1. Each pair [a, b] in pairs means a and b are friends. Friendship is transitive: a friend of a friend is in the same group.
Write count_groups(n, pairs) that returns the number of separate friend groups. A person with no friends is a group of one.