6.6 Number of Connected Components in an Undirected Graph

6.6.1 Problem Metadata

6.6.2 Description

Given n nodes labeled 0..n-1 and a list of undirected edges, return the number of connected components in the graph.

6.6.3 Examples

Example 1: Two Components

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: Component 1: [0,1,2], Component 2: [3,4]

Example 2: Single Component

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: 1
Explanation: All nodes are connected in a single component

Example 3: All Isolated Nodes

Input: n = 5, edges = []
Output: 5
Explanation: No edges, so 5 isolated components

6.6.4 Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ edges.length ≤ 10^5
  • Each edge is [u, v] where 0 ≤ u, v < n
  • No self-loops and no duplicate edges
  • Graph is undirected

6.6.5 Solution - DFS Traversal

6.6.5.1 Walkthrough

Build an adjacency list upfront, then use DFS to explore each component. Each time DFS returns, we’ve discovered a new connected component.

Step 1: Build Adjacency List

Pre-build the graph structure so we can efficiently query neighbors without rescanning edges. Since the graph is undirected, add edges in both directions: when we see edge [u, v], add v to u’s neighbor list and u to v’s neighbor list.

Step 2: Iterate Through All Nodes

For each node \(i\) from 0 to \(n-1\), check if it’s been visited: - If already visited, skip it (already counted as part of a previous component) - If unvisited, start a DFS from that node and increment component count

Step 3: DFS Traversal

When DFS starts from an unvisited node, it recursively explores all reachable neighbors, marking each as visited. Once DFS returns, all nodes in that component have been marked visited, ensuring we count each component exactly once.

Example Trace: \(n = 5\), edges \(= [[0,1],[1,2],[3,4]]\)

After building the graph:

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

Iteration: - \(i = 0\) (unvisited): Call dfs(0) → marks 0, 1, 2 as visited → result = 1 - \(i = 1\) (visited): Skip - \(i = 2\) (visited): Skip - \(i = 3\) (unvisited): Call dfs(3) → marks 3, 4 as visited → result = 2 - \(i = 4\) (visited): Skip

Return 2 ✓

6.6.5.2 Analysis

  • Time Complexity: O(V \(+\) E) — Each node is visited once and each edge is traversed once during DFS
  • Space Complexity: O(V \(+\) E) — Adjacency list uses O(V \(+\) E) space; recursion stack uses at most O(V) in worst case (linear chain)

6.6.5.3 Code - Java

public int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    boolean[] visited = new boolean[n];
    int result = 0;

    // Pre-build adjacency list
    for(int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }

    // Build edges in graph (undirected)
    for(int[] edge: edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }

    // Count components: each unvisited node starts a new component
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            dfs(i, graph, visited);
            result++;
        }
    }

    return result;
}

private void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    List<Integer> neighbors = graph.get(node);
    visited[node] = true;

    // Traverse all unvisited neighbors
    for(int neighbor: neighbors) {
        if(!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

6.6.6 Solution - BFS Traversal

6.6.6.1 Walkthrough

Use BFS with a queue to explore each component level-by-level. The algorithm is similar to DFS but uses an explicit queue instead of recursion.

Step 1: Build Adjacency List

Same as DFS—pre-build the graph with both directions for undirected edges.

Step 2: Iterate Through All Nodes

For each unvisited node, start a BFS and increment the component count. This ensures each component is counted exactly once.

Step 3: BFS Exploration

Enqueue the starting node and mark it visited. While the queue is not empty: - Dequeue a node - For each unvisited neighbor, mark it visited and enqueue it - Continue until queue is empty (entire component explored)

Example Trace: \(n = 5\), edges \(= [[0,1],[1,2],[3,4]]\)

Component 1: - Start BFS at node 0: enqueue 0, mark visited - Dequeue 0: neighbors are [1] → mark 1, enqueue 1 - Dequeue 1: neighbors are [0, 2] → 0 visited, mark 2, enqueue 2 - Dequeue 2: neighbors are [1] → 1 visited - Queue empty → result = 1

Component 2: - Start BFS at node 3: enqueue 3, mark visited - Dequeue 3: neighbors are [4] → mark 4, enqueue 4 - Dequeue 4: neighbors are [3] → 3 visited - Queue empty → result = 2

Return 2 ✓

6.6.6.2 Analysis

  • Time Complexity: O(V \(+\) E) — Each node is visited once and each edge is traversed once
  • Space Complexity: O(V \(+\) E) — Adjacency list uses O(V \(+\) E) space; queue uses at most O(V) in worst case

6.6.6.3 Code - Java

public int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    boolean[] visited = new boolean[n];
    int result = 0;

    // Pre-build adjacency list
    for(int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }

    // Build edges in graph (undirected)
    for(int[] edge: edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }

    // Count components: each unvisited node starts a new component
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            bfs(i, graph, visited);
            result++;
        }
    }

    return result;
}

private void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while(!queue.isEmpty()) {
        int node = queue.poll();
        for(int neighbor: graph.get(node)) {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

6.6.7 Solution - Union Find

6.6.7.1 Walkthrough

Initialize each node as its own component. Process every edge by unioning the two endpoints. Each successful union (where the two nodes were in different components) reduces the component count by one. The final count is the answer.

Key insight: Start with n components (one per node). Each union() that merges two distinct components decrements the count. After processing all edges, the remaining count equals the number of connected components.

Example trace: \(n = 5\), edges \(= [[0,1],[1,2],[3,4]]\)

Initial: components = 5
         parent = [0, 1, 2, 3, 4]

Process [0,1]: find(0)=0, find(1)=1 → different → union, components = 4
               parent = [1, 1, 2, 3, 4]

Process [1,2]: find(1)=1, find(2)=2 → different → union, components = 3
               parent = [1, 2, 2, 3, 4]

Process [3,4]: find(3)=3, find(4)=4 → different → union, components = 2
               parent = [1, 2, 2, 4, 4]

Result: 2

6.6.7.2 Analysis

  • Time Complexity: O(E \(\cdot\) \(\alpha\)(n)) \(\approx\) O(E) — each edge triggers one union/find operation with near-constant cost due to path compression and union by rank
  • Space Complexity: O(n) — parent and rank arrays only; no adjacency list needed

Comparison with DFS/BFS:

Union-Find DFS / BFS
Space O(n) O(n + E) — needs adjacency list
Handles dynamic edges Yes No
Conceptual model Merge sets Explore graph

Union-Find is more space-efficient here because it processes edges directly without building an adjacency list.

6.6.7.3 Implementation Steps

  1. Initialize parent[i] = i and rank[i] = 0 for all nodes. Set components = n.
  2. For each edge [u, v]:
    • If find(u) != find(v): call union(u, v) and decrement components.
  3. Return components.

6.6.7.4 Code - Java

public int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    int[] rank = new int[n];

    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int components = n;

    for (int[] edge : edges) {
        if (union(parent, rank, edge[0], edge[1])) {
            components--;
        }
    }

    return components;
}

private int find(int[] parent, int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]); // path compression
    }
    return parent[x];
}

private boolean union(int[] parent, int[] rank, int a, int b) {
    int rootA = find(parent, a);
    int rootB = find(parent, b);

    if (rootA == rootB) return false; // already in same component

    if (rank[rootA] < rank[rootB]) {
        parent[rootA] = rootB;
    } else if (rank[rootB] < rank[rootA]) {
        parent[rootB] = rootA;
    } else {
        parent[rootB] = rootA;
        rank[rootA]++;
    }

    return true;
}