Practice › Graphs
Number of Connected Components
Medium · Graphs · Asked at Amazon, Google, Microsoft, LinkedIn
Count the connected components of an undirected graph.
Input
First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).
Output
The number of components.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2·10^5
DFS/BFS from every unvisited node, or use Disjoint Set Union.
Example 1
Input
5 3 1 2 2 3 4 5
Output
2
Example 2
Input
3 0
Output
3
Hints
- Start a BFS/DFS from any unvisited node — it marks exactly one whole component.
- Count how many times you had to start a new search. (Disjoint Set Union works too: components = n − successful unions.)
Approach
Build an adjacency list. For every node 1..n that isn't visited yet, increase the counter and run a BFS that marks everything reachable from it. Each node and edge is processed once. The BFS uses an explicit queue, so large graphs can't overflow the call stack the way recursive DFS can.
Complexity: O(n + m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<bool> seen(n + 1, false);
int components = 0;
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
components++;
queue<int> q;
q.push(s);
seen[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u])
if (!seen[v]) {
seen[v] = true;
q.push(v);
}
}
}
cout << components << "\n";
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
adj[u].append(v)
adj[v].append(u)
seen = [False] * (n + 1)
components = 0
for s in range(1, n + 1):
if seen[s]:
continue
components += 1
seen[s] = True
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if not seen[v]:
seen[v] = True
q.append(v)
print(components)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
adj.get(u).add(v);
adj.get(v).add(u);
}
boolean[] seen = new boolean[n + 1];
int components = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
components++;
seen[s] = true;
q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u))
if (!seen[v]) {
seen[v] = true;
q.add(v);
}
}
}
System.out.println(components);
}
}Solve Number of Connected Components online · All practice problems