Connected components

How does Connected components work?

Keep one visited set for the entire run. It is never reset between walks.

Loop over every node in the graph. Skip any node that is already marked.

An unmarked node begins a new component. Add one to the counter.

Run a full walk from that node. Everything it reaches belongs to this component.

The walk marks everything it touches. So none of those can start a walk later.

When the loop ends, the counter holds the number of groups. Every node was visited once.

1. count = 0, visited = {}Six nodes, with edges 0-1, 1-2 and 3-4.
2. walk from 0Node 0 is unmarked, so a component starts. The walk reaches 1 and 2.
3. count = 1, visited = {0, 1, 2}Nodes 1 and 2 are marked, so neither starts a walk.
4. walk from 3, count = 2Node 3 is unmarked. Its walk reaches node 4.
5. walk from 5, count = 3Node 5 has no edges. It is a component on its own.

function countComponents(n, adj) {
    const visited = new Set();
    let count = 0;
    for (let start = 0; start < n; start++) {
        if (visited.has(start)) continue;
        count++;
        const stack = [start];
        visited.add(start);
        while (stack.length) {
            const node = stack.pop();
            for (const next of adj[node] || []) {
                if (!visited.has(next)) {
                    visited.add(next);
                    stack.push(next);
                }
            }
        }
    }
    return count;
}

A worked example of Connected components

Count the islands in a grid

A grid holds land cells and water cells. Count how many separate islands it contains.

Cells only touch up, down, left and right.

Walk the grid cell by cell. An unmarked land cell starts a new island.

Flood the whole island from there, marking as you go. The number of floods is the answer.

function numIslands(grid) {
    let count = 0;

    function sink(r, c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
        if (grid[r][c] !== "1") return;

        grid[r][c] = "0"; // marked in place, so no visited set is needed
        sink(r + 1, c);
        sink(r - 1, c);
        sink(r, c + 1);
        sink(r, c - 1);
    }

    for (let r = 0; r < grid.length; r++) {
        for (let c = 0; c < grid[0].length; c++) {
            if (grid[r][c] === "1") {
                count++;   // one new island
                sink(r, c);
            }
        }
    }

    return count;
}

When should you use Connected components?

These phrases in a problem statement point here:

• •count separate groups/islands/clusters
• •graph may be disconnected
• •how many connected pieces
• •friend circles
• •label connected regions

What is Connected components confused with?

• Graph BFS / DFS: That is the walk itself. This page is the loop that starts one walk per group.
• Union-find (disjoint set): Union-find answers while the edges are still arriving. Flood fill needs the whole graph up front.
• Bipartite check (two-coloring): A two-colouring runs the same walk while carrying a colour. It answers a different question.
• Topological sort (Kahn's algorithm): Ordering needs directed edges and no cycles. Components treat every edge as undirected.

Common mistakes with Connected components

• Resetting the visited set per walk

  One component then gets counted many times. A single set covers the whole run.

• Counting nodes instead of walks

  The answer is how many walks started. It is not how many nodes each one touched.

• Marking after descending

  A cycle then sends the walk straight back before the mark exists. Mark before you descend.

• Recursing over a very large grid

  A million-cell island overflows the call stack. Use an explicit stack or a queue.

Which interview problems use Connected components?

• Number of islands: One flood per unmarked land cell.
• Number of provinces: The graph arrives as an adjacency matrix.
• Connected components in an undirected graph: The plain form, over an edge list.
• Max area of island: Return the size of the largest walk, not the count.
• Count sub-islands: Count it only if every cell is land in the other grid too.
• Making a large island: Label each island, then test every water cell.
• Redundant connection: Union-find answers this while the edges arrive.

What is the time and space complexity of Connected components?

O(V+E)

V nodes and E edges give O(V + E) in total. Each node is visited by exactly one walk.