Code Logo

Count Connected Components

Published at25 Jul 2026
Created by
DFS Medium 0 views
Like0

Given n nodes labeled from 0 to n-1 and an undirected edge list, count the number of connected components in the graph using DFS.

Build an adjacency list from the edges. Use a visited array. For each unvisited node, run DFS to visit all reachable nodes and increment the component count.

Time is O(n + e) where e is the number of edges. Space is O(n + e) for the adjacency list.

Example Input & Output

Example 1
Input
5,[[0,1],[1,2],[3,4]]
Output
2
Explanation

Two components: {0,1,2} and {3,4}

Example 2
Input
3,[]
Output
3
Explanation

No edges: each node is its own component

Example 3
Input
1,[]
Output
1
Explanation

Single node

Example 4
Input
3,[[0,1],[1,2]]
Output
1
Explanation

3 nodes, 2 edges: one component

Example 5
Input
4,[[0,1],[1,2],[2,3]]
Output
1
Explanation

Chain: one component

Algorithm Flow

Recommendation Algorithm Flow for Count Connected Components
Recommendation Algorithm Flow for Count Connected Components

Solution Approach

function solution(n, edges) {
  var adj = []; for (var i = 0; i < n; i++) adj[i] = [];
  for (var i = 0; i < edges.length; i++) {
    adj[edges[i][0]].push(edges[i][1]);
    adj[edges[i][1]].push(edges[i][0]);
  }
  var visited = []; for (var i = 0; i < n; i++) visited[i] = false;
  function dfs(u) { visited[u] = true; for (var j = 0; j < adj[u].length; j++) { if (!visited[adj[u][j]]) dfs(adj[u][j]); } }
  var count = 0;
  for (var i = 0; i < n; i++) { if (!visited[i]) { count++; dfs(i); } }
  return count;
}

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int n, int[][] e) {
        List<Integer>[] adj=new ArrayList[n];for(int i=0;i<n;i++)adj[i]=new ArrayList<>();
        for(int[] p:e){adj[p[0]].add(p[1]);adj[p[1]].add(p[0]);}
        boolean[] v=new boolean[n];int c=0;
        for(int i=0;i<n;i++){if(!v[i]){c++;dfs(i,adj,v);}}
        return c;
    }
    void dfs(int u,List<Integer>[] adj,boolean[] v){
        v[u]=true;for(int w:adj[u]){if(!v[w])dfs(w,adj,v);}
    }
}