90.Number of Connected Components

MediumBlind 75Graphs · 11/19

Problem

You are given n nodes labelled 0 to n - 1 and a list of undirected edges, where edges[i] = [a, b] connects node a and node b.

Return the number of connected components in the graph. A connected component is a maximal group of nodes in which every node can reach every other node through some path. An isolated node with no edges counts as its own component.

Examples

Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: {0, 1, 2} form one component and {3, 4} form another.

Input:  n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Explanation: All five nodes are linked in a single chain.

Input:  n = 4, edges = []
Output: 4
Explanation: No edges, so every node is its own component.

Constraints

1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= a, b < n, a != b
There are no repeated edges.

💡 Key Insight

Every traversal (DFS or BFS) started from an unvisited node discovers exactly one whole component, so the answer is the number of traversals we have to start. Union-Find gives an even simpler view: begin with n separate components and decrement the count every time an edge merges two different sets — edges inside an existing set change nothing.

DFS

TimeO(V + E)SpaceO(V + E)

Intuition

Build an adjacency list. Walk through the nodes; whenever we meet one that has not been visited yet, we have found a new component — run a DFS from it to mark every node in that component as visited so we never count it again.

Algorithm

Build adj as a list of neighbour lists (add both directions for each edge).
Keep boolean[] visited and components = 0.
For each node i from 0 to n - 1: if not visited, increment components and DFS from i, marking everything reachable.
Return components.

Visualization

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

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

i=0 unvisited -> components=1, DFS marks 0,1,2
i=1,2 already visited
i=3 unvisited -> components=2, DFS marks 3,4
i=4 already visited
answer = 2

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[n];
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++; // a fresh, unseen component
                dfs(i, adj, visited);
            }
        }
        return components;
    }

    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        for (int next : adj.get(node)) {
            if (!visited[next]) {
                dfs(next, adj, visited);
            }
        }
    }
}

Complexity

Time: O(V + E) — every node and edge is visited once.
Space: O(V + E) — adjacency list plus a recursion stack up to depth V.

BFS

TimeO(V + E)SpaceO(V + E)

Intuition

Same counting idea, but explore each component with a queue instead of recursion. This avoids stack-overflow risk on a long chain of 2000 nodes.

Algorithm

Build the adjacency list.
For each unvisited node i: increment components, push i into a queue and mark it visited.
While the queue is non-empty, pop a node and push all its unvisited neighbours (marking them when pushed).
Return components.

Visualization

start BFS at 0: queue=[0]
pop 0 -> push 1          queue=[1]
pop 1 -> push 2          queue=[2]
pop 2 -> nothing new     queue=[]     component #1 = {0,1,2}
start BFS at 3: queue=[3]
pop 3 -> push 4, pop 4   queue=[]     component #2 = {3,4}

Code

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[n];
        int components = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            components++;
            visited[i] = true;
            queue.offer(i);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int next : adj.get(node)) {
                    if (!visited[next]) {
                        visited[next] = true; // mark on push to avoid duplicates
                        queue.offer(next);
                    }
                }
            }
        }
        return components;
    }
}

Complexity

Time: O(V + E) — each node is enqueued once, each edge scanned twice.
Space: O(V + E) — adjacency list and queue.

Union-FindOptimal

TimeO(V + E · α(V))SpaceO(V)

Intuition

Start with n singleton sets, so components = n. Process each edge: if its endpoints already share a root, the edge is redundant; otherwise union the two sets and decrement components. With path compression and union by rank, each operation is nearly O(1), and we never need an adjacency list.

Algorithm

parent[i] = i, rank[i] = 0, components = n.
For each edge [a, b]: find rootA and rootB.
If rootA != rootB, attach the shorter tree under the taller one and do components--.
Return components.

Dry Run

flowchart TD
    S["components = 5<br/>sets: {0} {1} {2} {3} {4}"] -->|"edge 0-1: roots 0,1 differ"| A["components = 4<br/>{0,1} {2} {3} {4}"]
    A -->|"edge 1-2: roots 0,2 differ"| B["components = 3<br/>{0,1,2} {3} {4}"]
    B -->|"edge 3-4: roots 3,4 differ"| C["components = 2<br/>{0,1,2} {3,4}"]
    C --> R["return 2"]

Code

java

class Solution {
    private int[] parent;
    private int[] rank;

    public int countComponents(int n, int[][] edges) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int components = n;
        for (int[] e : edges) {
            if (union(e[0], e[1])) {
                components--; // two different sets merged into one
            }
        }
        return components;
    }

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

    private boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false; // already connected
        }
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
        return true;
    }
}

Complexity

Time: O(V + E · α(V)) — α is the inverse Ackermann function, effectively constant.
Space: O(V) — only the parent and rank arrays.

Complexity Comparison

Approach	Time	Space
DFS	O(V + E)	O(V + E)
BFS	O(V + E)	O(V + E)
Union-Find	O(V + E · α(V))	O(V)

Common Pitfalls

Adding each edge in only one direction to the adjacency list — the graph is undirected, so DFS would miss nodes.
Forgetting isolated nodes: iterate over all n nodes, not just nodes that appear in edges.
In Union-Find, decrementing components on every edge instead of only when the roots differ.
Marking nodes visited when they are popped (not pushed) in BFS, which enqueues the same node many times.