323 · Number of Connected Components

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [a_i, b_i] indicates an edge between a_i and b_i. Return the number of connected components.

Graph & Component Clusters

idle

INVARIANT Component Partitioning Invariant: The vertices of an undirected graph partition into disjoint equivalence classes. Outer loop over unvisited nodes launches a DFS marking the entire component. Alternatively, DSU starts with n components and decrements by 1 per successful merge. Time: O(V + E), Space: O(V + E).

Components:0

Current Node:-

Visited:[]

Press Run to begin.

0 / 0

Java 21 Solution (DFS)

INTERVIEW SCRIPT

How to Explain Connected Components in Undirected Graph

1. Core Pattern Recognition

"This is the quintessential connected component problem. Vertices are $0..n-1$. We build an adjacency list and count how many DFS explorations are initiated from the outer loop."

2. DFS vs Disjoint Set Union (DSU)

"Both approaches are interview favorites: DFS achieves $O(V + E)$ using adjacency lists; DSU achieves $O(V + E \cdot \alpha(V))$ starting with $count = n$ and subtracting 1 for each successful union."

3. Outer Loop Invariant

"Whenever !visited[i] in the outer loop, city $i$ belongs to a new component. Increment count++ and exhaustively visit its entire component before continuing."

4. Complexity Mastery

"Total time is $O(V + E)$ since every vertex and edge is touched twice (once from each endpoint). Space is $O(V + E)$ to store the adjacency list and $O(V)$ for the visited array."