Компоненты связности

O(V+E)

Проходим по каждому узлу; от каждого ещё не посещённого запускаем полный обход, который помечает всю его группу, и считаем это одной компонентой. Число обходов, нужных чтобы покрыть граф, и есть число отдельных частей.

Сигналы

посчитать число отдельных групп/островов/кластеровграф может быть несвязнымсколько связных частейкруги друзейразметить связные области

Шаблон

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

Похоже, но не то

Обход графа BFS / DFS: Один BFS/DFS от одного старта покрывает только компоненту, содержащую этот узел. Чтобы посчитать компоненты, нужен проход по всем узлам с новым обходом от каждого ещё не посещённого.
Union-find: Компоненты подходят для графа, зафиксированного до начала подсчёта. Union-find нужен, когда рёбра продолжают прибывать со временем и между слияниями надо отвечать 'одна ли это группа?'.

V, E до ~1e5, граф может быть несвязным, нужно посчитать число отдельных частей -> O(V+E): проход и его обходы вместе касаются каждого узла и ребра один раз.

Изучить этот паттерн