Number of Connected Components

Difficulty: Medium

Problem

A network has n computers labeled 0 to n−1, joined by a list of undirected cables given as pairs in edges. Return how many separate clusters the network splits into, where machines in the same cluster can reach each other through cables and machines in different clusters cannot. You counted islands on a grid; this is the same question on a real node-and-edge graph. The same cable may be listed more than once, and a cable may join a computer to itself; neither changes the answer, because the visited set skips a node that is already claimed.

Example

Input: n = 6, edges = [[0,1],[1,2],[4,5]]
Output: 3
Explanation: Computers {0, 1, 2} are chained together, {4, 5} share a cable, and computer 3 has no cables at all, so it is a cluster by itself. Three clusters → 3.

Brute-force approach

The honest brute force is to walk from every node: for each node, start a fresh walk with its own empty notebook, collect everything that walk can reach, and count the different groups at the end. It gives the right answer, but it throws work away, because every member of a group re-walks the whole group. On the statement's graph (n = 6, edges = [[0,1],[1,2],[4,5]]) the six walks claim 3 + 3 + 3 + 1 + 2 + 2 = 14 nodes in all, for 6 nodes. On a chain of a thousand nodes every walk reaches all 1,000, so 1,000 x 1,000 = 1,000,000 claims. The fix is one shared visited set: a node claimed by one flood is never walked again, so each node is claimed exactly once and each cable is looked at twice, O(V + E).

Time complexity: O(V x (V + E)) in the worst case: 14 claims on the example, 1,000,000 on a chain of 1,000 · Space complexity: O(V + E) for the adjacency list and one walk's notebook

Trade-offs

Every node re-walks its whole group: a group of size k is walked k times
A chain of 1,000 nodes costs 1,000,000 claims against 1,000 with a shared visited set

Optimal approach

Key insight: The scan discovers each piece exactly once; the flood erases the rest of the piece from future discovery. Islands, without the grid.

Build the adjacency list, then scan every node: each unvisited one starts a new component (count it) and a BFS claims all of its members.

Steps

Build the adjacency list (both directions per edge)
For each node 0..n−1: if visited, skip
Otherwise count += 1 and BFS from it, marking every reachable node
Return the count

Time complexity: O(V + E) · Space complexity: O(V + E)

Pseudocode

function countComponents(n, edges):
    adj = adjacency list (both directions)
    visited = empty set
    count = 0
    
    for node in 0 .. n-1:
        if node in visited:
            ____
        count = count + ____
        
        queue = deque([node])
        visited.add(node)
        while queue not empty:
            cur = queue.popleft()
            for nb in adj[cur]:
                if nb not in ____:
                    visited.add(nb)
                    queue.append(____)
    
    return count

Hints

Already-claimed nodes get skipped. Which keyword moves the roll call along?
The counter ticks exactly once per NEW piece, by how much?
The flood must not re-claim marked nodes, check membership where?
Newly discovered members join the flood, append which node?

Complexity questions

What is the time complexity?

O(V + E): every node scanned once, every edge crossed at most twice. The scan is O(V); across ALL floods combined, each node is dequeued once and each undirected edge examined from both ends: O(V + E) total.

What is the space complexity?

O(V + E): adjacency list plus visited plus queue. Adjacency stores 2E entries, visited up to V, the queue up to V. O(V + E).

Each edge you ADD to a graph changes the component count how?

Decreases it by 1 if it joins two different pieces; changes nothing if both endpoints were already in the same piece. A bridge between two pieces merges them (count −1). An edge inside one piece just adds a cycle (count unchanged). This is why n nodes with k edges have AT LEAST n − k components, and exactly that many when there are no cycles. Check it exhaustively: of the 32,768 labelled graphs on six nodes, n minus edges is the true component count on only 2,932, exactly the graphs with no cycle (the forests); on all the others there are more components than that.

How would Union-Find solve this problem?

Start with n singleton sets; union the endpoints of each edge; the number of remaining distinct sets is the answer. Every successful union merges two pieces. Starting from n pieces, the count ends at n − (number of merging unions). Union-Find shines when edges arrive as a STREAM, no rebuild needed per query.

Check your understanding of Number of Connected Components

What exactly is a connected component?

A maximal group of nodes that can all reach each other through edges. A component is a whole 'piece': every node in it can reach every other, and nothing outside it is reachable. 'Maximal' matters, {0,1} alone isn't a component if 2 is also attached.

How does this problem differ from Number of Islands?

Same scan-and-flood pattern, but the graph comes as an EDGE LIST, so we build an adjacency list first instead of using grid directions. Identical skeleton: scan all nodes, count each unvisited piece, flood it. The only change is the representation step of the checklist: adjacency list instead of grid + directions.

Why must the visited set be SHARED across all the floods?

So a node claimed by one component's flood is never re-counted when the scan reaches it later. The counter only fires on unvisited nodes. Because flood #1 marks ALL of its component's members, the scan skips them silently. Each piece gets exactly one count.

n = 4 with NO edges at all. How many components?

4: every isolated node is its own piece. A lonely node is a complete (tiny) component: it reaches everything it can reach, itself. Four isolated nodes → four components. This is why we scan NODES, not edges.

In an undirected graph, the edge [0,1] must appear in the adjacency list as...

Both adj[0] → 1 AND adj[1] → 0. Undirected means both ways. Store it once and floods can enter a component from one side but not exit the other, pieces get miscounted. Two appends per edge, always.