There are n people 0 .. n-1. Each pair (a, b) in links says a and b know each other, and "is connected to" is transitive: if a knows b and b knows c, all three are in the same group.
Implement count_groups(n, links) -> int: the number of separate groups after processing every link.
Write the union-find yourself with a plain parent list:
find(x): followparentup to the root (the node that is its own parent). Make it iterative and compress the path.union(a, b): find both roots; if they differ, point one at the other and decrease the group count by one.
count_groups(5, [(0, 1), (1, 2), (3, 4)]) # 2 {0, 1, 2} and {3, 4}
count_groups(4, [(0, 1), (1, 0), (2, 2)]) # 3 repeated and self links change nothing
count_groups(3, []) # 3 everyone alone
Constraints: 0 <= n <= 2 * 10^5, up to 2 * 10^5 links. The tests include one long chain, so a recursive find without path compression will be slow or hit the recursion limit.
Show hint
start with count = n and subtract one only when union joins two different roots.