Connected Components in an Undirected Graph – Solution & Complexity

• The question asks for the number of connected groups, not the size of the biggest one and not whether the whole graph is connected.
• Isolated vertices count as one-node components, so starting from n separate sets is often the cleanest mental model.

• You can build an adjacency list and run DFS or BFS from every unvisited node. Each new search marks one whole component.
• That is already linear and perfectly acceptable in many interviews, but union-find is the more reusable pattern when the input is primarily an edge stream.

• Initialize every node as its own parent, so the graph starts with n components.
• For each edge, find the roots of both endpoints. If the roots differ, union them and decrement the component count. If the roots are already equal, that edge stays inside an existing component and changes nothing.
• Path compression plus union by rank keeps the finds almost constant-time in practice.

Each edge is processed once, and amortized union-find operations are effectively constant time.

• Forgetting that nodes with no incident edges still count as separate components.
• Decrementing the component counter for every edge instead of only for edges that actually merge two different roots.
• Follow-up: for a stream of edge insertions, union-find is usually preferable because it updates the answer incrementally without rebuilding adjacency lists or rerunning graph traversals.