Count connected components while edges arrive dynamically. Best structure?
Options
- Union-Find with path compression and ranks (Correct option)
- A stack that stores the vertices of each group
- A binary search tree of all the vertices seen
- A Bloom filter that stores the edges so far
Answer
Union-Find (disjoint set) with path compression and union by rank
Why
Union-Find keeps groups of elements. find(x) returns the group leader; union(a, b) merges two groups.
When an edge a-b arrives, union them; the number of components drops by one if they were in different groups.
With path compression and union by rank, each operation is almost O(1). Also used for Kruskal's minimum spanning tree.
Remember
Dynamic 'are these connected?' → Union-Find.