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
Union 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. This approach avoids explicit graph traversal and provides near O(1) amortized union and find operations.
Optimal Approach
Initialize 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. After processing all edges, the remaining count represents the number of connected components.
Time
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
| 6 | def find(i):
|
| 7 | while i != par[i]:
|
| 8 | par[i] = par[par[i]]
|
| 9 | i = par[i]
|
| 10 | return i
|
Objective
To locate the root parent of a node efficiently, flattening the tree structure along the way.
Key Insight
Path compression shortens the path from any node to its root by making every node on the path point directly to the root. This optimization drastically reduces the time complexity of subsequent find operations, approaching amortized O(1).
Interview Quick-Check
Core Logic
Path compression in find ensures that the tree remains flat, enabling near-constant time queries.
Common Pitfalls & Bugs
Not applying path compression leads to tall trees and slower find operations.
State & Boundaries
The loop continues until a node is its own parent, which is the root of the set.
Perform Union by Rank to Merge Sets and Update Component Count
| 12 | def union(n1, n2):
|
| 13 | p1, p2 = find(n1), find(n2)
|
| 15 | if p1 == p2:
|
| 16 | return 0
|
| 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
|
Objective
To merge two distinct sets by connecting their roots, maintaining balanced trees and updating the count of connected components.
Key Insight
Union by rank attaches the smaller tree under the larger one, preserving shallow tree height. When two sets merge, the total number of connected components decreases by one. Returning 1 or 0 from union indicates whether a merge occurred, enabling decrementing the component count accordingly.
Interview Quick-Check
Core Logic
Union merges two sets only if their roots differ, updating parent and rank arrays to maintain balanced trees.
Common Pitfalls & Bugs
Failing to check if roots are equal before union can cause incorrect merges and wrong component counts.
State & Boundaries
Rank updates reflect the new size of the merged set, ensuring future unions remain efficient.
Iterate Over Edges to Union Connected Nodes and Track Component Count
| 26 | res = n
|
| 27 | for n1, n2 in edges:
|
| 28 | res -= union(n1, n2)
|
| 29 | return res |
Objective
To process each edge, merge connected nodes' sets, and decrement the count of connected components accordingly.
Key Insight
Starting with n components (each node isolated), each successful union reduces the count by one. By iterating through all edges and applying union, the algorithm efficiently computes the final number of connected components without explicit graph traversal.
Interview Quick-Check
Core Logic
Subtracting the result of union from the component count accurately tracks the number of connected components.
Common Pitfalls & Bugs
Not decrementing the count only when union merges distinct sets leads to incorrect component counts.
State & Boundaries
Looping over all edges ensures all connections are accounted for.
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.
if rank[p1] > rank[p2]:If the rank of the first root is greater, attach the second root under the first.
Attaching the smaller tree under the larger keeps the tree shallow, optimizing future find operations.
return 1Return 1 to indicate a successful union and component count decrement.
Returning 1 signals that two sets merged, allowing the caller to update the connected components count.
par = [i for i in range(n)]Initialize the parent array where each node is its own parent.
This initialization represents each node as a separate set, forming the foundation for union-find operations.
def union(n1, n2):Define the union function to merge two sets if distinct.
Union combines two disjoint sets into one, which is the core operation for tracking connected components.
p1, p2 = find(n1), find(n2)Find the root parents of both nodes.
Determining the roots is necessary to check if the nodes are already connected or need merging.
par[p2] = p1Update the parent of the second root to the first root.
This merges the two sets by linking their roots.
else:Otherwise, attach the first root under the second root.
This alternative union maintains balanced trees by attaching the smaller set under the larger one.
par[p1] = p2Update the parent of the first root to the second root.
This completes the union by linking the roots appropriately.
return resReturn the final count of connected components.
After processing all edges, the remaining count represents the number of distinct connected components in the graph.
rank = [1] * nInitialize the rank array with 1 for each node.
Rank tracks the size of each set to optimize union by attaching smaller trees under larger ones, reducing tree height and improving efficiency.
def find(i):Define the find function to locate the root parent of a node.
The find function identifies the representative of the set a node belongs to, which is essential for determining if two nodes are connected.
return iReturn the root parent of the node.
Returning the root parent identifies the set representative, which is used to determine connectivity.
return 0Return early to avoid unnecessary union operations.
This prevents incorrect decrementing of component count and redundant tree modifications.
rank[p1] += rank[p2]Increase the rank of the first root by the size of the second set.
Updating rank maintains accurate size information for balanced unions.
rank[p2] += rank[p1]Increase the rank of the second root by the size of the first set.
Maintaining accurate rank information ensures efficient future unions.
res = nInitialize the result as the total number of nodes (each node is its own component).
Starting with n components reflects the initial state before any unions.
while i != par[i]:Continue traversing up the tree until the root parent is found.
The loop ensures traversal to the root, which is the node that is its own parent, marking the set representative.
for n1, n2 in edges:Iterate over each edge connecting two nodes.
Processing all edges ensures all connections are considered for merging sets.
i = par[i]Move up to the parent node for the next iteration.
This step progresses the search towards the root parent in the find operation.
Test Your Understanding
Why does the union operation decrement the count of connected components only when two nodes belong to different sets?
Because union merges two previously separate sets into one, reducing the total number of disjoint sets by one. If the nodes are already in the same set, no merge occurs and the count remains unchanged.
Related Problems
Graphs 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