Count clusters of linked instruments

Question

You have n instruments (labeled 0..n-1) and a list of links, where each link says two instruments belong to the same group. Links are transitive (if A links B and B links C, all three are one group). Count how many distinct groups exist. Return the number of connected groups.

Accepted Answer

Use a disjoint-set (union-find) structure. Each instrument starts as its own group. For each link, merge the two groups. find follows parent pointers to a group's representative, with path compression to flatten the tree over time. After processing all links, count distinct representatives. Tracing n=5 with those links: 0,1,2 collapse to one representative and 3,4 to another, so the count is 2. Time nearly O(n + m) with path compression (inverse-Ackermann per operation), space O(n). Edge cases: zero links means n singleton groups; self-links are harmless (find(a) == find(a)); duplicate links …

Count clusters of linked instruments

Your answer

More Coding questions