Connected components

O(V+E)

Sweep every node; from each one still unvisited, run a full traversal that marks its whole group and count that as one component. The number of traversals needed to cover the graph is the number of separate pieces.

Signals

count separate groups/islands/clustersgraph may be disconnectedhow many connected piecesfriend circleslabel connected regions

Template

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

Looks similar, isn't

Graph BFS / DFS: A single BFS/DFS from one start only covers the component containing that node. Counting components needs a sweep over every node, starting a fresh traversal from each one still unvisited.
Union-find: Components suit a graph that is fixed before you start counting. Union-find is for edges that keep arriving over time, where you need 'same group?' answered between merges.

V, E up to ~1e5, graph may be disconnected, need the count of separate pieces -> O(V+E): the sweep and its traversals together touch every node and edge once.

Learn this pattern