Number of Connected Components in an Undirected Graph

NeetCode: Number of Connected Components in an Undirected Graph · LeetCode: 323. Number of Connected Components in an Undirected Graph · Difficulty: Medium

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

Example

Text

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

Brute force: adjacency matrix and DFS

Build an n x n boolean matrix where matrix[u][v] says whether the edge exists. Then count components the standard way: for each node not yet visited, count one component and DFS to mark everything reachable. Finding a node's neighbors means scanning a matrix row, which costs O(n) even for a node with a single edge.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int countComponents(int n, int[][] edges) {
        boolean[][] matrix = new boolean[n][n];
        for (int[] e : edges) {
            matrix[e[0]][e[1]] = true;
            matrix[e[1]][e[0]] = true;
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int start = 0; start < n; start++) {
            if (visited[start]) {
                continue;
            }
            count++;
            visited[start] = true;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            while (!stack.isEmpty()) {
                int node = stack.pop();
                for (int next = 0; next < n; next++) {
                    if (matrix[node][next] && !visited[next]) {
                        visited[next] = true;
                        stack.push(next);
                    }
                }
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.countComponents(5, new int[][]{{0, 1}, {1, 2}, {3, 4}}));
        System.out.println(s.countComponents(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}}));
        System.out.println(s.countComponents(3, new int[][]{}));
        System.out.println(s.countComponents(0, new int[][]{}));
    }
}

Output

Time: O(n^2) (building and scanning the matrix). Space: O(n^2).

Optimal: union-find, counting merges

Start with n components (every node alone). Each edge either joins two different components, reducing the count by one, or connects two nodes that are already together, changing nothing. So after processing all edges the count is the answer. Union-find with path compression and union by size handles each edge in O(alpha(n)).

A DFS or BFS over an adjacency list is also O(n + E). Union-find is used here because the same structure solves Redundant Connection and Graph Valid Tree.

The structure keeps each node's parent in an int[]. find returns the root of a node's set. union attaches the smaller set under the larger and returns false when both nodes already share a root.

Java

class Dsu {
    private final int[] parent;
    private final int[] size;

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

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) {
            return false;
        }
        if (size[ra] < size[rb]) {
            int tmp = ra;
            ra = rb;
            rb = tmp;
        }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
}

class Solution {
    public int countComponents(int n, int[][] edges) {
        Dsu dsu = new Dsu(n);
        int count = n;
        for (int[] e : edges) {
            if (dsu.union(e[0], e[1])) {
                count--;
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.countComponents(5, new int[][]{{0, 1}, {1, 2}, {3, 4}}));
        System.out.println(s.countComponents(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}}));
        System.out.println(s.countComponents(3, new int[][]{}));
        System.out.println(s.countComponents(0, new int[][]{}));
    }
}

Output

Time: O(n + E * alpha(n)). Space: O(n).