Number of Connected Components in an Undirected Graph
MediumUpdated: Aug 2, 2025
Practice on:
Problem
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Examples
Example 1:
0 3
| |
1 --- 2 4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.
Example 2:
0 4
| |
1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
Note
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Solution
Method 1 - DFS on Graph
We can use normal DFS to find number of components. But it is good to use Union Find Data structure.
An undirected graph is represented by:
- A number of nodes,
n(labelled0ton-1). - A list of
edges, each representing a connection between any two nodes.
To find the number of connected components:
- Think of this problem as identifying clusters of connected nodes in the graph.
- Use Graph Traversal Algorithms:
- DFS (Depth First Search) or BFS (Breadth First Search) to explore each connected component fully.
- Maintain an array to track visited nodes. Each time you encounter an unvisited node, it's the start of a new connected component.
Algorithm
- Create an adjacency list to store the graph from the input edges.
- Use a
visitedarray to track whether a node has been visited. - Perform a DFS or BFS from each unvisited node, marking all connected nodes as visited during traversal. For each traversal, increment the connected components count.
- Return the count of connected components.
Code
Java
class Solution {
public int countComponents(int n, int[][] edges) {
// Create adjacency list
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
// Visited set to track visited nodes
boolean[] visited = new boolean[n];
// DFS Helper function
void dfs(int node) {
visited[node] = true;
for (int nei : graph.get(node)) {
if (!visited[nei]) {
dfs(nei);
}
}
}
int ans = 0;
// Iterate through all nodes
for (int i = 0; i < n; i++) {
if (!visited[i]) {
ans++; // A new component
dfs(i); // Explore the entire component
}
}
return ans;
}
}
Python
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
# Create adjacency list
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# Visited set to keep track of visited nodes
visited = [False] * n
def dfs(node: int) -> None:
# Mark current node as visited
visited[node] = True
for nei in graph[node]:
if not visited[nei]:
dfs(nei)
ans = 0
# Iterate through all nodes
for i in range(n):
if not visited[i]:
ans += 1 # A new component
dfs(i) # Explore the entire component
return ans
Complexity
- ⏰ Time complexity:
O(V + E)due to DFS - 🧺 Space complexity:
O(V + E), Storing adjacency list usesO(V + E)space, and visited array usesO(V)space.
Method 2 - Union Find
This problem can be solved by using union-find beautifully. Initially, there are n nodes. The nodes that are involved in each edge is merged.
We can use Disjoint Set - Union by Rank Implementation
Here is the approach:
- Treat each node as its own component initially.
- Use the Union-Find/Disjoint Set data structure to group connected nodes together:
- Union Operation: Merge two sets containing two connected nodes.
- Find Operation: Identify the "parent" or representative of a set, enabling us to determine if two nodes belong to the same set.
- Path Compression: Optimisation to ensure that all nodes in a set point directly to their representative, making future lookups faster.
- After processing all edges, count the number of distinct sets (connected components).
Code
Java
class Solution {
public int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.getCount();
}
class UnionFind {
private int[] parent;
private int[] rank;
private int count;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int node) {
int res = node;
while (res != parent[res]) {
parent[res] = parent[parent[res]]; // Path compression
res = parent[res];
}
return res;
}
public boolean union(int u, int v) {
int root1 = find(u);
int root2 = find(v);
if (root1 == root2) {
return false;
}
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
rank[root1] += rank[root2]; // Add size
} else {
parent[root1] = root2;
rank[root2] += rank[root1]; // Add size
}
count--;
return true;
}
public int getCount() {
return count;
}
}
}
Python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
self.count = n
def find(self, node):
res = node
while res != self.parent[res]:
self.parent[res] = self.parent[self.parent[res]] # Path compression
res = self.parent[res]
return res
def union(self, u, v) -> bool:
root1, root2 = self.find(u), self.find(v)
if root1 == root2:
return False
if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
self.rank[root1] += self.rank[root2]
else:
self.parent[root1] = root2
self.rank[root2] += self.rank[root1]
self.count -= 1
return True
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.count
Complexity
- ⏰ Time complexity:
O(E * α(V))Eis the number of edges.α(V)is the inverse Ackermann function, almost constant for practical purposes.
- 🧺 Space complexity:
O(V)as space is used to store the parent and rank.