Number of Connected Components in an Undirected Graph

Number of Connected Components in an Undirected Graph

What is this problem about?

The Number of Connected Components in an Undirected Graph problem gives you n nodes labeled 0 to n-1 and a list of undirected edges. Find the number of connected components — groups of nodes where every node is reachable from every other node in the group. This is a foundational graph connectivity problem solvable with DFS, BFS, or Union-Find.

Why is this asked in interviews?

Apple, Twitter, Meta, Amazon, LinkedIn, TikTok, and Google ask this as the standard graph connectivity problem. It tests knowledge of Union-Find vs DFS/BFS approaches and their trade-offs. The union find, BFS, graph, and DFS interview pattern is at the core, and it's frequently asked as a building block before harder graph problems.

Algorithmic pattern used

Union-Find (most efficient). Initialize each node as its own component (n components). For each edge (u, v), union the two nodes. If they were in different components, decrement the component count. Return the final count.

DFS alternative: Mark nodes as visited, do DFS from each unvisited node, each DFS invocation = one component.

Example explanation

n=5, edges=[(0,1),(1,2),(3,4)].

• Initially 5 components.
• Union(0,1): 4 components.
• Union(1,2): 3 components.
• Union(3,4): 2 components. Answer = 2 components: {0,1,2} and {3,4}.

Common mistakes candidates make

• Treating the graph as directed (undirected edges need both directions).
• Not initializing visited array for DFS (revisiting nodes).
• Union-Find without path compression (slower for large inputs).
• Forgetting isolated nodes (each unconnected node is its own component).

Interview preparation tip

Connected components is one of the most reused graph primitives. Master both Union-Find (great for dynamic edge additions) and DFS (simpler to implement for static graphs). For interviews, Union-Find with path compression and union-by-rank is the cleanest and most impressive. Practice this as a sub-problem: it appears inside Minimum Spanning Tree, graph coloring, and network connectivity problems.