Approach Summary
DFS/BFS to mark connected nodes, or Union-Find to merge edges. Count distinct components.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Breadth-First Search (BFS) | O(V + E) | O(V) | Iterates through all vertices, launching a queue-based BFS traversal to mark all nodes within each connected component. |
| 2 Approach 2: Disjoint Set Union (Union-Find) (Optimal) | O(V + E * α(V)) | O(V) | Initializes N disjoint sets and unifies edge endpoints with path compression and rank, decrementing component count on each successful merge. |
Step 1: Baseline
Approach 1: Breadth-First Search (BFS)
Time: O(V + E)
Space: O(V)
1. Build adjacency list from edges. 2. Maintain `visited` array of size N initialized to false. 3. Loop `i` from 0 to N - 1. If not visited, increment component count. 4. Push `i` to queue and mark `visited[i] = true`. 5. While queue has elements, pop `curr` and check each neighbor. If unvisited, mark visited and enqueue. 6. Return total component count.
Approach 1: Breadth-First Search (BFS) Implementation
Approach 1: Breadth-First Search (BFS)
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[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
Queue<Integer> q = new ArrayDeque<>();
q.add(i);
visited[i] = true;
while (!q.isEmpty()) {
int curr = q.poll();
for (int neighbor : adj.get(curr)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.add(neighbor);
}
}
}
}
}
return count;
}
}class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
queue<int> q;
q.push(i);
visited[i] = true;
while (!q.empty()) {
int curr = q.front(); q.pop();
for (int neighbor : adj[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
}
return count;
}
};from collections import deque
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)
visited = [False] * n
count = 0
for i in range(n):
if not visited[i]:
count += 1
visited[i] = True
q = deque([i])
while q:
curr = q.popleft()
for neighbor in adj[curr]:
if not visited[neighbor]:
visited[neighbor] = True
q.append(neighbor)
return countvar countComponents = function(n, edges) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const visited = new Array(n).fill(false);
let count = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
count++;
visited[i] = true;
const q = [i];
while (q.length > 0) {
const curr = q.shift();
for (const neighbor of adj[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
}
return count;
}; Step 2: Most Optimized
Approach 2: Disjoint Set Union (Union-Find) (Optimal)
Time: O(V + E * α(V))
Space: O(V)
1. Initialize `parent` array where `parent[i] = i` and component count = N. 2. Define `find(i)` with path compression: `parent[i] = find(parent[i])`. 3. For each edge (u, v): - `rootU = find(u)`, `rootV = find(v)`. - If `rootU != rootV`, merge by setting `parent[rootU] = rootV` and decrement `count--`. 4. When all edges are processed, return `count`. 5. Operates in nearly O(1) amortized time per operation.
Approach 2: Disjoint Set Union (Union-Find) (Optimal) Implementation
Approach 2: Disjoint Set Union (Union-Find) (Optimal)
class Solution {
public int countComponents(int n, int[][] edges) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int count = n;
for (int[] e : edges) {
int ru = find(parent, e[0]), rv = find(parent, e[1]);
if (ru != rv) {
parent[ru] = rv;
count--;
}
}
return count;
}
int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
}class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
int count = n;
auto find = [&](auto& self, int x) -> int {
return parent[x] == x ? x : parent[x] = self(self, parent[x]);
};
for (auto& e : edges) {
int ru = find(find, e[0]), rv = find(find, e[1]);
if (ru != rv) {
parent[ru] = rv;
count--;
}
}
return count;
}
};class Solution:
def countComponents(self, n: int, edges: list[list[int]]) -> int:
parent = list(range(n))
rank = [1] * n
components = n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
ru, rv = find(u), find(v)
if ru != rv:
if rank[ru] > rank[rv]:
parent[rv] = ru
elif rank[ru] < rank[rv]:
parent[ru] = rv
else:
parent[rv] = ru
rank[ru] += 1
components -= 1
return componentsvar countComponents = function(n, edges) {
const parent = Array.from({length: n}, (_, i) => i);
let count = n;
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (const [u, v] of edges) {
const ru = find(u), rv = find(v);
if (ru !== rv) {
parent[ru] = rv;
count--;
}
}
return count;
};Edge Cases to Watch
- Isolated vertices with no edges — each counts as its own component of size 1 (total components = n)
- Fully connected graph (clique or single spanning tree) — exactly 1 component
- Empty edge list — exactly n components
- Self-loops or parallel duplicate edges — handled cleanly without affecting component counts
Algorithmic Pattern
View Pattern Guide →
Master the Graphs Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Graphs pattern.
How to Recognize This Pattern
- Count connected components in undirected graph
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V)
Tags
Graph DFS Union Find
Frequently Asked Questions
What is the optimal time and space complexity for Number of Connected Components in Undirected Graph?
The optimal solution for Number of Connected Components in Undirected Graph achieves O(V + E) runtime complexity and requires O(V) auxiliary space. Time Complexity is O(V + E) for BFS / DFS, where V is the number of vertices and E is the number of edges, as each vertex and edge is examined at most twice. For Union-Find with path compression and union by rank, the time is O(V + E * alpha(V)) where alpha is the inverse Ackermann function (effectively constant). Space Complexity is O(V + E) to store the adjacency representation or O(V) for the visited array / parent array.
How do I identify that Number of Connected Components in Undirected Graph requires the Graphs pattern?
In technical interviews, look for key problem signals: Count connected components in undirected graph. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Graphs strategy.
What critical edge cases must be handled in Number of Connected Components in Undirected Graph?
Essential edge cases to verify include: Isolated vertices with no edges — each counts as its own component of size 1 (total components = n); Fully connected graph (clique or single spanning tree) — exactly 1 component; Empty edge list — exactly n components; Self-loops or parallel duplicate edges — handled cleanly without affecting component counts. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Number of Connected Components in Undirected Graph?
Number of Connected Components in Undirected Graph is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at LinkedIn, Google, Amazon.