Компоненты связности: обход из каждой непосещённой вершины или union-find
Elman Huseynov · 2026-11-14
Короткий ответ. Компоненты связности это группы вершин. Внутри группы из любой вершины можно дойти до любой. Считаются они просто. Идём по всем вершинам, из каждой непосещённой запускаем обход. Считаем запуски. Время O(V + E). Второй способ это система непересекающихся множеств. Ниже, когда какой способ брать, код на Python и разбор задач.
Что такое компоненты связности?
Неориентированный граф может распадаться на куски. Внутри куска все вершины соединены путями. Между кусками путей нет. Каждый такой кусок это компонента.
Граф из одного куска называют связным. Число компонент у него равно единице.
Изолированная вершина без рёбер это тоже компонента. Про неё часто забывают, когда граф задан только списком рёбер.
На сетке компонента это остров: группа клеток, соседних по сторонам. Задача Number of Islands ровно про это.
countComponents(7, {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3, 5], 5: [4], 6: []})Считаем отдельные группы среди 7 вершин. Одно множество visited живёт весь запуск и не сбрасывается.
Страница паттерна: когда его применять и шаблон на шести языках
Как считаются компоненты связности обходом?
- Заводим набор visited.
- Идём по всем вершинам. Вершина уже посещена, пропускаем.
- Иначе это новая компонента. Запускаем DFS или BFS и помечаем всё достижимое.
- Считаем запуски. Это и есть ответ.
Каждая вершина и каждое ребро смотрятся один раз. Отсюда O(V + E).
Какой обход брать, DFS или BFS, значения не имеет. Оба помечают всё достижимое. DFS через явный стек короче в коде.
Как это выглядит на примере?
Пять вершин, рёбра 0-1, 1-2, 3-4. Вершина 0 не посещена: обход помечает 0, 1, 2. Счётчик 1. Вершины 1 и 2 пропускаем. Вершина 3 не посещена: обход помечает 3 и 4. Счётчик 2. Вершину 4 пропускаем. Ответ 2.
Добавим ребро 2-3. Тогда первый обход дойдёт до всех пяти вершин, и ответ станет 1.
Как написать подсчёт компонент связности на Python?
def count_components(n, edges):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = [False] * n
count = 0
for start in range(n):
if seen[start]:
continue
count += 1
stack = [start]
seen[start] = True
while stack: # DFS явным стеком
v = stack.pop()
for u in graph[v]:
if not seen[u]:
seen[u] = True
stack.append(u)
return count
def count_components_dsu(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
count = n
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
count -= 1 # два куска стали одним
return count
Вторая функция не строит список смежности. Она идёт по рёбрам и сливает группы. Каждое удачное слияние уменьшает счётчик.
Обход или система непересекающихся множеств: что брать?
| Признак | Обход DFS / BFS | Система непересекающихся множеств |
|---|---|---|
| Граф задан | Списком смежности или сеткой | Списком рёбер |
| Рёбра добавляются потоком | Нужен пересчёт | O(1) на ребро |
| Нужен список вершин компоненты | Есть сразу | Нужен отдельный проход |
| Память | Список смежности плюс visited | Один массив parent |
| Время | O(V + E) | O(E · α(V)), почти линейно |
Правило: граф статичный, берите обход. Рёбра приходят по одному и после каждого нужен ответ, берите множества.
На собеседовании чаще ждут обход. Он проще объясняется и не требует отдельной структуры. Множества называют как второй вариант.
Как решить Number of Provinces?
Матрица n на n, единица значит, что города связаны. Нужно число групп. Матрица это и есть список смежности. Запускаем подсчёт компонент. Соседи вершины i это все j с единицей в строке i. Время O(n²).
Как решить Graph Valid Tree?
Дерево это связный граф без циклов. Проверяем два условия: рёбер ровно n - 1 и компонента одна. Оба условия вместе исключают цикл. Считаем компоненты любым способом.
Вариант через множества ещё проще. union вернул False, значит ребро замкнуло цикл. Ответ нет.
Как решить задачу про число островов?
Сетка из нулей и единиц. Идём по всем клеткам. Нашли непосещённую единицу, запускаем обход из неё и помечаем весь остров. Считаем запуски. Соседи клетки это четыре клетки по сторонам, и перед чтением каждой проверяем границы.
Это те же компоненты связности, только граф задан неявно. Строить список смежности не нужно, соседи считаются на лету.
По каким словам в задаче узнать приём?
- «Число компонент», «число островов», «число групп друзей».
- «Связен ли граф», «является ли граф деревом».
- «Сколько рёбер добавить, чтобы граф стал связным».
- «Размер самой большой группы».
На каких ошибках ломается решение?
- Добавляют ребро только в одну сторону в неориентированном графе.
- Считают компоненты рекурсией на графе в миллион вершин.
- Забывают изолированные вершины, которых нет ни в одном ребре.
- Помечают посещённой при снятии со стека, и вершина попадает туда много раз.
Как объяснить приём на собеседовании?
Скажите: запускаю обход из каждой непосещённой вершины и считаю запуски. Назовите O(V + E). Потом упомяните второй способ и когда он лучше.
Для сетки скажите про явный стек. Для потока рёбер скажите про множества. Это два уточнения, которые ждут.
Отработать узнавание приёма можно на странице компоненты связности. Второй способ разобран на странице система непересекающихся множеств.
Вопросы и ответы
Как найти размер самой большой компоненты?
В обходе считайте помеченные вершины при каждом запуске. В множествах храните массив size и обновляйте его при слиянии.
Что такое компоненты сильной связности?
Это то же понятие для ориентированного графа. Путь должен быть в обе стороны. Считаются алгоритмами Косараю или Тарьяна. На собеседованиях встречаются редко.
Сколько рёбер нужно, чтобы соединить k компонент?
Ровно k - 1. Каждое ребро сливает две компоненты в одну.
Где компоненты связности встречаются в реальных системах?
В социальных сетях при поиске изолированных сообществ. В обработке изображений при выделении объектов. В проверке сети на разрывы между узлами.