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

Connected components

O(V+E)

Начинайте новый обход в каждой ещё не увиденной вершине. Каждый реально начатый обход означает ещё одну связную группу графа.

Elman HuseynovОбновлено 17 окт. 2026 г.

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

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

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

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

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

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

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

Источники: Википедия: Компонента связности графа

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

Подсчёт компонент связности

countComponents(7, {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3, 5], 5: [4], 6: []})

число над вершиной = номер её компоненты

stack (стек)

пусто

start = 0count = 0

Считаем отдельные группы среди 7 вершин. Одно множество visited живёт весь запуск и не сбрасывается.

1 / 29

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

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

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

Посчитать острова в сетке

В сетке лежат клетки суши и воды. Посчитайте, сколько в ней отдельных островов.

Клетки соприкасаются только сверху, снизу, слева и справа.

Идите по сетке клетка за клеткой. Непомеченная клетка суши открывает новый остров.

Залейте оттуда весь остров, помечая по пути. Число заливок и есть ответ.

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

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

Паттерн «Компоненты связности» нужен, когда в условии есть слова «посчитать число отдельных групп/островов/кластеров», «граф может быть несвязным» или «сколько связных частей». Решение на нём обычно укладывается в O(V+E).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Компоненты связности» чаще всего путают с этими паттернами: Обход графа BFS / DFS, Система непересекающихся множеств, Проверка двудольности (раскраска в два цвета) и Топологическая сортировка (алгоритм Кана).

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

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

Сбрасывают множество посещённых на каждый обход
Тогда одна компонента считается много раз. Одно множество живёт весь запуск.
Считают вершины вместо обходов
Ответ это число начатых обходов. А не число вершин, которых каждый коснулся.
Помечают после спуска
Тогда цикл вернёт обход назад раньше, чем пометка появится. Помечайте до спуска.
Идут рекурсией по огромной сетке
Остров на миллион клеток переполняет стек вызовов. Возьмите явный стек или очередь.

Паттерн «Компоненты связности» решает такие задачи с собеседований: Число островов, Число провинций, Компоненты связности неориентированного графа, Наибольшая площадь острова, Число подостровов, Создание большого острова и Лишнее ребро.

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