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.

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

No brute-force phase for graph problems, scan-and-flood IS the approach.

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 = [node]
        visited.add(node)
        while queue not empty:
            cur = queue.pop_front()
            for nb in adj[cur]:
                if nb not in ____:
                    visited.add(nb)
                    queue.push(____)
    
    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, push 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.

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.