Count Connected Components

Published at25 Jul 2026

Graph DFS Medium 1 views

Like0

Given an adjacency list representing an undirected graph with n nodes (0 to n-1), count the number of connected components. A connected component is a group of nodes that are reachable from each other through edges.

For example, with n=5 and edges [[0,1],[1,2],[3,4]], there are 2 components: {0,1,2} and {3,4}. With n=3 and no edges, there are 3 components (each node isolated). With n=0, return 0.

Connected components are fundamental to graph theory. They represent clusters of related data in social networks, isolated subgraphs in communication networks, and distinct regions in geographic data.

The solution uses DFS traversal: maintain a visited array, iterate through each node, and when an unvisited node is found, start a DFS from it and increment the component count. The DFS visits all reachable nodes, marking them as visited.

Edge cases include an empty graph (return 0), a fully connected graph (1 component), and completely disconnected nodes (each node is its own component).

Example Input & Output

Example 1

Input

5,[[0,1],[1,2],[3,4]]

Output

Explanation

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

Example 2

Input

3,[]

Output

Explanation

No edges: each node is its own component

Example 3

Input

1,[]

Output

Explanation

Single node

Example 4

Input

3,[[0,1],[1,2]]

Output

Explanation

3 nodes, 2 edges: one component

Example 5

Input

4,[[0,1],[1,2],[2,3]]

Output

Explanation

Chain: one component

Algorithm Flow

Recommendation Algorithm Flow for Count Connected Components

Solution Approach

Use DFS to visit all nodes in each component, counting components as you discover unvisited nodes.

function countComponents(n, edges)
  visited = array of n false values
  count = 0
  for i = 0 to n - 1
    if not visited[i]
      count = count + 1
      dfs(i)
  return count

Create an adjacency list from the edges. Maintain a visited boolean array. For each unvisited node, increment the component count and perform DFS to mark all nodes in that component as visited. Return the total count.

Time complexity is O(n + e), space complexity is O(n + e).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

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);}
    }
}

javascript

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

php

<?php
function solution($n,$e){$adj=array_fill(0,$n,[]);foreach($e as$p){$adj[$p[0]][]=$p[1];$adj[$p[1]][]=$p[0];}$v=array_fill(0,$n,false);$c=0;
    $dfs=function($u)use(&$dfs,$adj,&$v){$v[$u]=true;foreach($adj[$u]as$w){if(!$v[$w])$dfs($w);}};
    for($i=0;$i<$n;$i++){if(!$v[$i]){$c++;$dfs($i);}}return$c;
}

python

def solution(n,e):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    v=[False]*n
    def dfs(u):
        v[u]=True
        for w in adj[u]:
            if not v[w]:dfs(w)
    c=0
    for i in range(n):
        if not v[i]:c+=1;dfs(i)
    return c

rust

fn solution(n: i32, e: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for p in e {
        let a = p[0] as usize;
        let b = p[1] as usize;
        adj[a].push(b);
        adj[b].push(a);
    }
    let mut v = vec![false; n];
    let mut c = 0;
    for i in 0..n {
        if !v[i] {
            c += 1;
            let mut st = vec![i];
            while let Some(u) = st.pop() {
                if !v[u] {
                    v[u] = true;
                    for &w in &adj[u] {
                        if !v[w] {
                            st.push(w);
                        }
                    }
                }
            }
        }
    }
    c
}

typescript

function solution(n: number, e: number[][]): number {
  var adj: number[][] = [];
  for (var i = 0; i < n; i++) adj[i] = [];
  for (var i = 0; i < e.length; i++) {
    adj[e[i][0]].push(e[i][1]);
    adj[e[i][1]].push(e[i][0]);
  }
  var v: boolean[] = [];
  for (var i = 0; i < n; i++) v[i] = false;
  function dfs(u: number): void {
    v[u] = true;
    for (var j = 0; j < adj[u].length; j++) {
      if (!v[adj[u][j]]) dfs(adj[u][j]);
    }
  }
  var c = 0;
  for (var i = 0; i < n; i++) {
    if (!v[i]) {
      c++;
      dfs(i);
    }
  }
  return c;
}

Related Graph Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Count Connected Components

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

Garden Relay Count

Catalog Shelf Lineup

Ascending Manifest

Mountain Cabin Signal Range

Seaport Ferry Gate Control

City Bus Loop Access

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.