---
title: "Компоненты связности"
url: https://algopath.pro/ru/patterns/graph-components
language: ru
summary: "Начинайте новый обход в каждой ещё не увиденной вершине. Каждый реально начатый обход означает ещё одну связную группу графа."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

- **Обход графа BFS / DFS** - Это сам обход. Здесь описан цикл, запускающий по одному обходу на группу.
- **Система непересекающихся множеств** - Она отвечает, пока рёбра ещё приходят. Заливке нужен весь граф сразу.
- **Проверка двудольности (раскраска в два цвета)** - Раскраска ведёт тот же обход, но несёт цвет. Она отвечает на другой вопрос.
- **Топологическая сортировка (алгоритм Кана)** - Упорядочиванию нужны направленные рёбра без циклов. Компоненты считают любое ребро ненаправленным.

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

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

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

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

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

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

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

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

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

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

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

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

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

## JavaScript

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

## Python

```python
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
```

## PHP

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