Number of Connected Components in an Undirected Graph
Problem
Given an integer n representing the number of nodes labeled from 0 to n-1 and a list of undirected edges, return the number of connected components in the graph.
- 1 ≤ n ≤ 10⁴
- 0 ≤ edges.length ≤ 10⁴
- edges[i].length == 2
- 0 ≤ edges[i][j] < n
- No duplicate edges
- No self-loops
Example
n = 5, edges = [[0,1],[1,2],[3,4]]2Initially, there are 5 isolated nodes, so 5 components. The edge [0,1] connects nodes 0 and 1, reducing components to 4. The edge [1,2] connects node 2 to the component containing 0 and 1, reducing components to 3. The edge [3,4] connects nodes 3 and 4, reducing components to 2. No more edges remain, so the final count is 2.
Approach
Straightforward Solution
A brute-force approach would build an adjacency list and perform DFS or BFS from each unvisited node to count components. This approach is O(n + e) but requires graph traversal and bookkeeping.
Core Observation
The problem asks for the count of connected components in an undirected graph, which can be viewed as partitioning nodes into disjoint sets where each set represents a connected component.
Path to Optimal
PreviewUnion Find (Disjoint Set Union) is a data structure designed to efficiently track and merge disjoint sets. By initializing each node as its own set and unioning sets connected by edges, the number of connected components is the count of unique parents after all unions…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize Union Find with each node as its own parent and rank 1. For each edge, perform union operation to merge sets if they are distinct, decrementing the component count…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n + e * α(n))
Initialization takes O(n). Each union/find operation runs in nearly O(1) amortized time due to path compression and union by rank, where α(n) is the inverse Ackermann function, which grows extremely slowly and is practically constant.
Space
O(n)
Two arrays of size n are used to store parent and rank information, which scale linearly with the number of nodes.
Pattern Spotlight
Union Find (Disjoint Set Union)
When asked to find connected components or detect cycles in an undirected graph, model the problem as merging disjoint sets and use Union Find to efficiently track and combine these sets with near-constant time operations.
Solution
| 1 | class Solution:
|
| 2 | def countComponents(self, n: int, edges: list[list[int]]) -> int:
|
| 3 | par = [i for i in range(n)]
|
| 4 | rank = [1] * n
|
| 5 |
|
| 6 | def find(i):
|
| 7 | while i != par[i]:
|
| 8 | par[i] = par[par[i]]
|
| 9 | i = par[i]
|
| 10 | return i
|
| 11 |
|
| 12 | def union(n1, n2):
|
| 13 | p1, p2 = find(n1), find(n2)
|
| 14 |
|
| 15 | if p1 == p2:
|
| 16 | return 0
|
| 17 |
|
| 18 | if rank[p1] > rank[p2]:
|
| 19 | par[p2] = p1
|
| 20 | rank[p1] += rank[p2]
|
| 21 | else:
|
| 22 | par[p1] = p2
|
| 23 | rank[p2] += rank[p1]
|
| 24 | return 1
|
| 25 |
|
| 26 | res = n
|
| 27 | for n1, n2 in edges:
|
| 28 | res -= union(n1, n2)
|
| 29 | return res |
Step-by-Step Solution
Initialize Union Find Data Structures for Parent and Rank
| 3 | par = [i for i in range(n)]
|
| 4 | rank = [1] * n
|
Objective
To represent each node as its own set initially, preparing for efficient union and find operations.
Key Insight
Each node starts as its own parent, indicating separate sets. The rank array tracks the size of each set to optimize union operations by attaching smaller trees under larger ones, minimizing tree height and speeding up find operations.
Interview Quick-Check
Core Logic
Initializing parent to self and rank to 1 sets up the disjoint sets for efficient union-find operations.
State & Boundaries
Rank array stores the size of each set, which guides union to keep trees shallow.
Common Pitfalls & Bugs
Forgetting to initialize rank or parent arrays correctly can cause incorrect unions or infinite loops in find.
Implement Find with Path Compression to Identify Set Representatives
To locate the root parent of a node efficiently, flattening the tree structure along the way.
Perform Union by Rank to Merge Sets and Update Component Count
To merge two distinct sets by connecting their roots, maintaining balanced trees and updating the count of connected components.
Iterate Over Edges to Union Connected Nodes and Track Component Count
To process each edge, merge connected nodes' sets, and decrement the count of connected components accordingly.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
par[i] = par[par[i]]Apply path compression by pointing the current node directly to its grandparent.
Path compression flattens the tree structure, drastically reducing the time complexity of future find operations.
res -= union(n1, n2)Subtract the result of union from the component count.
Decrementing the count only when a union merges two distinct sets accurately tracks the number of connected components.
if p1 == p2:Return 0 if both nodes share the same root, indicating no merge needed.
If roots are equal, the nodes are already connected, so the component count should not change.
Full line-by-line criticality + rationale for all 22 lines available on Pro.
Test Your Understanding
Why does the union operation decrement the count of connected components only when two nodes belong to different sets?
See the answer with Pro.
Related Problems
Union Find pattern
Don't just read it. Drill it.
Reconstruct Number of Connected Components in an Undirected Graph from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Number of Connected Components in an Undirected Graph drill