Start with n elements (0 .. n-1), each in its own group. Apply a series of union
operations, then return the number of distinct groups remaining.
countGroups(n, unions)
Input format: n | unions, unions as a,b pairs. Output the final group count.
n=5, unions (0,1)(1,2)(3,4) // → 2 ({0,1,2}, {3,4})
n=4, no unions // → 4
n=3, unions (0,1)(0,2)(1,2) // → 1
Start with n singleton groups, repeatedly merge pairs, and want the final count of distinct groups. You could model this as a graph and run BFS/DFS after all unions to count connected components, but that means storing every union as an edge and doing a full traversal. Union-find is purpose-built for this pattern: merge groups, then answer membership questions.
Give every element a parent pointer. Initially each points to itself — its own root. To merge two groups, find each group's current root (follow parent pointers until reaching a self-pointing element) and point one root at the other. That single pointer change merges every member of both groups, since "which group am I in" is answered by "which root do I reach" — the find operation.
Naively following parent pointers could take a while if chains get long. Path compression fixes this: while walking up during a find, make nodes point closer to the root as you go. This flattens the tree so later finds on the same elements are nearly instant. Combined with union-by-size, the amortized cost per operation is essentially constant — bounded by the inverse Ackermann function, so slow-growing it's constant for any practical input.
def count_groups(n, unions):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
count = n
for a, b in unions:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
count -= 1
return count
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.