Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Start a BFS/DFS from any unvisited node — it marks exactly one whole component.
  2. 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