LeetCode · #323

Number of Connected Components Solution

Given n nodes and a list of undirected edges, find the number of connected components in the graph.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #323 (Premium)

🏗️

Pattern

Graph — Union-Find / DFS connected components

You have n nodes labeled 0 to n-1 and a list of undirected edges. Return the number of connected components in the graph. A connected component is a maximal set of nodes where every pair is reachable from every other.

Example

 Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2 // Component 1: 2 Component 2: 4 Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1 // All nodes are connected — one component 

Constraints

 • 1 ≤ n ≤ 2000 • 0 ≤ edges.length ≤ 5000 • edges[i].length == 2,  0 ≤ u, v < n,  u ≠ v • No duplicate edges 

Section Two · Approach 1

DFS — O(V+E)

Build an adjacency list. Iterate through all nodes. For each unvisited node, run a DFS to mark every reachable node as visited and increment the component count. The total count equals the number of connected components.

Why it works

Each DFS call discovers exactly one connected component — all nodes reachable from the starting node. The outer loop ensures every node is visited. The number of DFS calls from the outer loop equals the number of distinct components.

Why Union-Find is an alternative

Trade-off: DFS is simple and O(V+E) but requires building an adjacency list and O(V) call stack for deep graphs. Union-Find processes edges directly without building a graph — just iterate edges and merge components. Both are O(V+E); Union-Find is more elegant for dynamic edge-addition scenarios and avoids recursion.

Java — DFS connected components

 import java.util.*;
class Solution {
public int countComponents(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
boolean[] vis = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(adj, vis, i);
                count++;
            }
        }
return count;
    }
private void dfs(List<List<Integer>> adj, boolean[] vis, int v) {
        vis[v] = true;
for (int nb : adj.get(v))
if (!vis[nb]) dfs(adj, vis, nb);
    }
}

Python — DFS connected components

 class Solution:
def countComponents(self, n: int, edges: list[list[int]]) -> int:
        adj = [[] for _ in range(n)]
for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        vis = [False] * n
        count = 0 def dfs(node: int) -> None:
            vis[node] = True for nb in adj[node]:
if not vis[nb]: dfs(nb)
for i in range(n):
if not vis[i]:
dfs(i)
                count += 1 return count

Metric	Value
Time	O(V + E) — each node and edge visited once
Space	O(V + E) — adjacency list + O(V) visited + O(V) call stack

Section Three · Approach 2

Union-Find — O(V + E·α(V))

Start with n components (each node is its own component). For each edge [u, v], union their components. If they're already in the same component, do nothing. Otherwise, merge and decrement the component count. The final count is the answer.

💡 Mental model: Imagine n students each standing alone in a schoolyard. Each edge is a "friendship declaration" — when two students become friends, their entire friend groups merge into one. You start with n groups. Each friendship either merges two existing groups (count decreases by 1) or connects two already-in-the-same-group students (count stays the same). After processing all friendships, the number of remaining groups is your answer.

Algorithm — Union-Find with component counter

Initialize: parent[i] = i, rank[i] = 0, components = n.
For each edge [u, v]: if find(u) ≠ find(v), union them and components--.
Return components.

🎯 When to recognize this pattern:

"How many groups / connected components?" in an undirected graph.
Union-Find is ideal when edges arrive one by one and you need incremental connectivity.
It's also the backbone of Kruskal's MST algorithm.
Related problems: LC 200 (Number of Islands — grid version), LC 684 (Redundant Connection — find first cycle-creating edge), LC 547 (Number of Provinces — adjacency matrix variant).

Why start with n and decrement:

Every successful union merges two components into one — reducing the count by exactly 1.
If all edges connect already-connected nodes, the count stays at n.
This counting strategy avoids a final pass over parent[] to count distinct roots (which would also work but is less elegant).

Section Four · Trace

Visual Walkthrough

Trace Union-Find on n=5, edges=[[0,1],[1,2],[3,4]]. Expected: 2 components.

Connected Components — Union-Find (n=5, 3 edges)

Section Five · Implementation

Code — Java & Python

Java — Union-Find with path compression + rank

 class Solution {
int[] parent, rank;
public int countComponents(int n, int[][] edges) {
        parent = new int[n];
        rank   = new int[n];
for (int i = 0; i < n; i++) parent[i] = i; // each node is its own root int components = n;
for (int[] e : edges) {
int pu = find(e[0]), pv = find(e[1]);
if (pu != pv) {
union(pu, pv);
                components--; // merged two components
}
        }
return components;
    }
private int find(int x) {
if (parent[x] != x)
            parent[x] = find(parent[x]); // path compression return parent[x];
    }
private void union(int x, int y) {
if (rank[x] < rank[y]) parent[x] = y;
else if (rank[x] > rank[y]) parent[y] = x;
else { parent[y] = x; rank[x]++; }
    }
}

Python — Union-Find with path compression + rank

 class Solution:
def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent = list(range(n))
        rank   = [0] * n
def find(x: int) -> int:
if parent[x] != x:
                parent[x] = find(parent[x]) # path compression return parent[x]
def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
if px == py: return False if rank[px] < rank[py]: px, py = py, px
            parent[py] = px
if rank[px] == rank[py]: rank[px] += 1 return True
components = n
for u, v in edges:
if union(u, v):
                components -= 1 return components

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS / BFS	O(V + E)	O(V + E)	Builds full adjacency list; recursive DFS risks stack overflow for large V
Union-Find ← optimal	O(V + E·α(V))	O(V)	No adjacency list needed; near-constant per operation; handles dynamic edges

DFS vs Union-Find for counting components:

Both are valid and nearly identical in performance for this problem.
Choose DFS if you need to enumerate which nodes belong to which component.
Choose Union-Find if you only need the count, or if edges arrive dynamically (streaming).
In interviews, Union-Find for this problem signals knowledge of the DSU data structure — a strong signal.
DFS is simpler to code for someone less familiar with Union-Find.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No edges	`n=5, edges=[]`	Every node is its own component. Return n=5.
Fully connected	`n=3, edges=[[0,1],[1,2]]`	Two unions, each reduces count by 1. 3-2=1. Return 1.
Single node	`n=1, edges=[]`	One component trivially. Return 1.
Redundant edge	`n=3, edges=[[0,1],[1,2],[0,2]]`	Third edge [0,2]: find(0)==find(2) already (both root=0). No decrement. Count stays 1.
Many isolated nodes	`n=100, edges=[[0,1]]`	Only one union. 100-1=99 components.
0-indexed vs 1-indexed	Nodes labeled 0..n-1	Unlike LC 684 (1-indexed), this problem is 0-indexed. Parent array size = n (not n+1).

⚠ Common Mistake: Calling union(e[0], e[1]) directly without first checking if find(e[0]) != find(e[1]) and then decrementing unconditionally. If both nodes are already in the same component, you'd decrement the count when no merge happened — producing a count that's too low. Always check find(u) != find(v) before decrementing, or have union() return a boolean indicating whether a merge occurred.

← Back to Graph problems

LearningTree

LC 323 · Number of Connected Components — Solution & Explanation | DSA Guide