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

Компоненты связности: как это работает?

Держите одно множество посещённых на весь запуск. Между обходами оно не сбрасывается.

Пройдите по всем вершинам графа. Уже помеченные пропускайте.

Непомеченная вершина открывает новую компоненту. Прибавьте единицу к счётчику.

Запустите из неё полный обход. Всё, до чего он дошёл, входит в эту компоненту.

Обход помечает всё, чего коснулся. Значит ничто из этого не начнёт обход позже.

Когда цикл кончился, в счётчике лежит число групп. Каждая вершина посещена один раз.

1. счёт = 0, посещённые = {}Шесть вершин, рёбра 0-1, 1-2 и 3-4.
2. обход из 0Вершина 0 не помечена, значит открылась компонента. Обход доходит до 1 и 2.
3. счёт = 1, посещённые = {0, 1, 2}Вершины 1 и 2 помечены, поэтому обход не начинают.
4. обход из 3, счёт = 2Вершина 3 не помечена. Её обход доходит до вершины 4.
5. обход из 5, счёт = 3У вершины 5 нет рёбер. Она сама себе компонента.

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

Компоненты связности: когда применять?

Эти формулировки в условии ведут сюда:

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

Компоненты связности: с чем путают?

• Обход графа BFS / DFS (Graph BFS / DFS): Это сам обход. Здесь описан цикл, запускающий по одному обходу на группу.
• Система непересекающихся множеств (Union-find (disjoint set)): Она отвечает, пока рёбра ещё приходят. Заливке нужен весь граф сразу.
• Проверка двудольности (раскраска в два цвета) (Bipartite check (two-coloring)): Раскраска ведёт тот же обход, но несёт цвет. Она отвечает на другой вопрос.
• Топологическая сортировка (алгоритм Кана) (Topological sort (Kahn's algorithm)): Упорядочиванию нужны направленные рёбра без циклов. Компоненты считают любое ребро ненаправленным.

Компоненты связности: частые ошибки

• Сбрасывают множество посещённых на каждый обход

  Тогда одна компонента считается много раз. Одно множество живёт весь запуск.

• Считают вершины вместо обходов

  Ответ это число начатых обходов. А не число вершин, которых каждый коснулся.

• Помечают после спуска

  Тогда цикл вернёт обход назад раньше, чем пометка появится. Помечайте до спуска.

• Идут рекурсией по огромной сетке

  Остров на миллион клеток переполняет стек вызовов. Возьмите явный стек или очередь.

Компоненты связности: задачи с собеседований

• Число островов: По одной заливке на каждую непомеченную клетку суши.
• Число провинций: Граф приходит матрицей смежности.
• Компоненты связности неориентированного графа: Чистая форма, по списку рёбер.
• Наибольшая площадь острова: Возвращается размер наибольшего обхода, а не их число.
• Число подостровов: Считать только если каждая клетка суша и во второй сетке.
• Создание большого острова: Пометьте острова, потом проверьте каждую клетку воды.
• Лишнее ребро: Здесь ответ даёт система непересекающихся множеств.

Компоненты связности: сложность по времени и памяти

O(V+E)

V вершин и E рёбер дают в сумме O(V + E). Каждую вершину посещает ровно один обход.