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.

Sources: Wikipedia: Component (graph theory)

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;
}

function countComponents(n: number, adj: number[][]): number {
    const visited = new Set<number>();
    let count = 0;
    for (let start = 0; start < n; start++) {
        if (visited.has(start)) continue;
        count++;
        const stack: number[] = [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;
}

def count_components(n, adj):
    visited = set()
    count = 0
    for start in range(n):
        if start in visited:
            continue
        count += 1
        stack = [start]
        visited.add(start)
        while stack:
            node = stack.pop()
            for nxt in adj.get(node, []):
                if nxt not in visited:
                    visited.add(nxt)
                    stack.append(nxt)
    return count

function countComponents(int $n, array $adj): int {
    $visited = [];
    $count = 0;
    for ($start = 0; $start < $n; $start++) {
        if (isset($visited[$start])) continue;
        $count++;
        $stack = [$start];
        $visited[$start] = true;
        while ($stack) {
            $node = array_pop($stack);
            foreach ($adj[$node] ?? [] as $next) {
                if (!isset($visited[$next])) {
                    $visited[$next] = true;
                    $stack[] = $next;
                }
            }
        }
    }
    return $count;
}

    public static int countComponents(int n, List<List<Integer>> adj) {
        Set<Integer> visited = new HashSet<>();
        int count = 0;
        for (int start = 0; start < n; start++) {
            if (visited.contains(start)) continue;
            count++;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            visited.add(start);
            while (!stack.isEmpty()) {
                int node = stack.pop();
                for (int next : adj.get(node)) {
                    if (visited.add(next)) stack.push(next);
                }
            }
        }
        return count;
    }

    public static int CountComponents(int n, List<List<int>> adj) {
        var visited = new HashSet<int>();
        int count = 0;
        for (int start = 0; start < n; start++) {
            if (visited.Contains(start)) continue;
            count++;
            var stack = new Stack<int>();
            stack.Push(start);
            visited.Add(start);
            while (stack.Count > 0) {
                int node = stack.Pop();
                foreach (int next in adj[node]) {
                    if (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?

Use Connected components when the problem statement says “count separate groups/islands/clusters”, “graph may be disconnected” or “how many connected pieces”. A solution built on it usually runs in O(V+E).

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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Connected components confused with?

Connected components is most often confused with Graph BFS / DFS, Union-find (disjoint set), Bipartite check (two-coloring) and Topological sort (Kahn's algorithm).

• 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?

Interview problems solved with Connected components include Number of islands, Number of provinces, Connected components in an undirected graph, Max area of island, Count sub-islands, Making a large island and Redundant connection.

• 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?

The target complexity of Connected components is O(V+E).

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