Number of Connected Components in an Undirected Graph

The problem

You are given node_count nodes, numbered 0 to node_count - 1, and a list of undirected edges, where [first, second] joins nodes first and second. Return how many separate pieces the graph has. A piece, or connected component, is a group of nodes that can all reach each other, and cannot reach any node outside the group.

Example 1

Input: node_count = 6, edges = [[0, 1], [1, 2], [3, 4]]

Output: 3

0, 1 and 2 form one piece, 3 and 4 another. Node 5 has no edges, so it is a piece on its own.

Example 2

Input: node_count = 4, edges = [[0, 1], [1, 2], [2, 3]]

Output: 1

The edges chain all four nodes together.

Example 3

Input: node_count = 3, edges = []

Output: 3

No edges, so every node is its own piece.

Constraints

• 1 ≤ node_count ≤ 2000 (call it V)
• 0 ≤ edges.length ≤ 5000 (call it E)
• No edge joins a node to itself, and no edge appears twice.

Clarifying questions

Does a node with no edges count?

Yes. It is a piece of size one, like node 5 in Example 1.

Can the edges form loops?

Yes. A loop does not change the count, but the search must not visit a node twice.

Are the edges directed?

No. Each edge can be walked both ways.

Can the same edge appear twice?

No.

Spot the pattern

A piece is everything you can reach from one node. “What can I reach from here?” is answered by graph search. Counting the pieces means counting how many separate searches it takes to reach every node. It is the same idea as counting islands in a grid, on a plain list of edges instead.

Solutions

Search from each new nodeO(V + E)

Show all

There is only one approach worth showing. Every node and every edge must be looked at, and this looks at each a fixed number of times. Union-find gives the same count at about the same cost.

Search from each new node O(V + E)

The idea

First turn the edge list into a list of neighbors for each node.

Then go through the nodes in order. If a node is already marked, an earlier search reached it, so it is in a piece we have counted. If it is not marked, nothing before it could reach it, so it starts a new piece: add 1 to the count, and run a search from it that marks every node it reaches.

Why it is correct: each search marks exactly one whole piece, because it reaches every node joined to the start and nothing else. Every node is in some piece, and a search starts only at a node whose piece has no marks yet. So there is one search per piece.

Walkthrough

pieces

0

stack top →

empty

1. neighbors = neighbor lists built from edges
2. for start in 0 .. node_count - 1:
3. if seen[start]: continue
4. pieces += 1; mark start; stack = [start]
5. while stack:
6. node = stack.pop()
7. for each unseen neighbor of node: mark neighbor; stack.push(neighbor)
8. return pieces

Build each node's neighbor list from the edges. Then go through the nodes 0 to 5. A node no search has reached yet starts a new piece.

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Graph search: start a search at every node not seen yet, count one piece,
    // and mark everything the search reaches. Each node and edge is handled a few times.
    public int countComponents(int nodeCount, int[][] edges) {
        List<List<Integer>> neighbors = new ArrayList<>();
        for (int i = 0; i < nodeCount; i++) neighbors.add(new ArrayList<>());
        for (int[] edge : edges) {
            neighbors.get(edge[0]).add(edge[1]);
            neighbors.get(edge[1]).add(edge[0]);
        }
        boolean[] seen = new boolean[nodeCount];
        int pieces = 0;
        for (int start = 0; start < nodeCount; start++) {
            if (seen[start]) continue;
            // Not reached by any earlier search, so it starts a new piece.
            pieces++;
            seen[start] = true;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            while (!stack.isEmpty()) {
                int node = stack.pop();
                for (int neighbor : neighbors.get(node)) {
                    if (!seen[neighbor]) {
                        seen[neighbor] = true;
                        stack.push(neighbor);
                    }
                }
            }
        }
        return pieces;
    }
}

Big O

Time O(V + E)Space O(V + E)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Building the lists reads each edge once. The outer for runs once per node. Inside the searches, the while loop pops one node per run, and the inner for looks at each of its neighbors. Each of these is a fixed job, so 1 step.

   1. neighbors = neighbor lists built from edges
   2. for start in 0 .. node_count - 1:
   3. if seen[start]: continue
   4. pieces += 1; mark start; stack = [start]
   5. while stack:
   6. node = stack.pop()
   7. for each unseen neighbor of node: mark neighbor; stack.push(neighbor)
   8. return pieces

2. 2 Count the runs on Example 1

   The table has one column per run of the outer loop. Three runs start a search, and the other three skip a node that is already marked. The second row is how many nodes that search popped.

   3 edges + 6 starts + 6 pops (3 + 2 + 1) + 6 neighbor looks = 21 steps.

   start	node 0	node 1	node 2	node 3	node 4	node 5
   outer loop	search	skip	skip	search	skip	search
   pops in its search	3	0	0	2	0	1

   total

   3 edges + 6 starts + 6 pops + 6 looks = 21

3. 3 Write the count for any n

   A node is pushed only when it is first marked, so over all the searches together each node is popped once. Each edge is in two neighbor lists, so the looks add up to 2 × E:

   E (build) + V (starts) + V (pops) + 2 × E (looks) = 2 × V + 3 × E steps

   Check it with Example 1: 2 × 6 + 3 × 3 = 21. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the 3. What is left is V + E. The searches run inside a loop, but they do not multiply: together they visit each node once, no matter how many searches there are.

   So the time is O(V + E).

5. S Space: count the extra memory the same way

   The neighbor lists hold 2 × E entries. The seen flags and the stack hold at most V each. So the space is O(V + E).

   neighbor lists (2 × E entries)seen (V)stack (up to V)

Common mistake

Counting edges instead of searches

It is tempting to answer V minus the number of edges, since each edge joins two nodes. That only works when there are no loops. With edges 0–1, 1–2 and 2–0, the third edge joins nothing new, and V − E undercounts.

Tested at the limits

2,000 random graphs of 1 to 8 nodes and up to 8 edges, from no edges to every pair joined. Search from each new node gave the same count every time as a simple union-find check written in the test.

Largest inputs	Result
2,000 nodes and 5,000 edges (the most allowed): a long line plus extra edges, so it is all one piece. Search from each new node.	Under 0.01 s, and about 0.24 MB of extra memory: the neighbor lists for 5,000 edges, plus the seen marks, O(V + E).
2,000 nodes and no edges: 2,000 pieces of one node each. Search from each new node.	Under 0.01 s, and about 0.13 MB of extra memory: 2,000 empty neighbor lists and 2,000 tiny searches.