Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
Algorithms

Connected Components Count

EasyJul 5, 2026graphdfsconnected-components

Counting components is the same stack DFS as `hasPath`, run from every node in the graph, with one twist: `exploreGraph` returns 0 or 1 instead of a node list, so the total becomes a running sum. What keeps a component from being counted more than once is a single `visited` set shared across every call, not any per-component bookkeeping.

The problem

Implement `connectedComponentsCount(graph)` where `graph` is an adjacency list (`{ node: [neighbours] }`). Return how many separate connected components it has — the two-cluster graph (`0`/`1`/`5`/`8` linked together, `2`/`3`/`4` linked together) should report `2`, and a graph mixing two isolated nodes with one connected pair (`a: [], b: [], c: ['d'], d: ['c']`) should report `3`.

Unlike `hasPath`/`undirectedPath`, this isn't a yes/no about two specific nodes — it has to visit every node in the graph via `for...in` and, for each one, decide whether it already belongs to a component that's been counted or is the start of a new one.

The approach

The `for...in` loop tries every key in `graph` as a potential DFS start, but `visited` is declared once outside the loop and threaded into every `exploreGraph` call as an argument — that's the entire trick. The first node of a component to reach `exploreGraph` runs the full stack-based traversal and marks every reachable node visited; every later node from that same component hits `if (visited.has(source)) return 0` immediately and contributes nothing further.

`exploreGraph` reuses the exact iterative stack DFS from `hasPath`/`dfs` — push a starting node, pop, walk its neighbours, push whichever aren't visited yet — but repurposes the return value: `1` means 'this call just discovered a new component', `0` means 'this node was already accounted for'. Summing those across the outer loop is the whole algorithm — counting by side effect instead of collecting an explicit list of components.

Isolated nodes fall out for free: `a: []` still gets pushed as `source`, the inner `for` over `graph[node]` simply never runs, and the function still returns `1` — a component of size one is still a component.

The solution

js
export function connectedComponentsCount(graph) {
    const visited = new Set()
    let noOfComponents = 0
    for (let node in graph) {
        noOfComponents += exploreGraph(graph, node, visited)
    }
    return noOfComponents
}

export function exploreGraph(graph, source, visited) {
    if (visited.has(source)) return 0
    visited.add(source)
    const stack = [source]
    while (stack.length) {
        const node = stack.pop()
        for (let neighbour of graph[node]) {
            if (!visited.has(neighbour)) {
                visited.add(neighbour)
                stack.push(neighbour)
            }

        }
    }
    return 1
}

Time O(V + E)Space O(V)

All entries