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

Граф может распадаться на несколько изолированных «кусков». Учимся находить их обходом и решать задачи об «островах».

Компонента связности — максимальный набор вершин, попарно достижимых друг из друга; граф разбивается на компоненты, между которыми нет рёбер.

Зачем это нужно

Реальные графы редко связны целиком: социальная сеть распадается на группы, карта — на материки, поле игры — на области. Вопрос «сколько отдельных кусков?» или «какие вершины в одном куске?» возникает постоянно. Классические формулировки: «сколько островов на карте?», «сколько групп друзей?», «связен ли граф?». Все они решаются одним приёмом — обходом, который «закрашивает» каждую компоненту. Это прямое и важное применение BFS/DFS.

Идея «на пальцах»

Алгоритм прост: идём по всем вершинам. Встретив непосещённую — запускаем из неё обход (BFS или DFS), который пометит всю её компоненту. Каждый новый запуск обхода = новая компонента. Считаем число запусков — получаем число компонент. Заодно можно присвоить каждой вершине номер её компоненты.

n = 7
edges = [(0, 1), (1, 2), (3, 4), (5, 6)]
g = [[] for _ in range(n)]
for u, v in edges:
    g[u].append(v); g[v].append(u)

seen = [False] * n
comp_id = [-1] * n        # номер компоненты для каждой вершины
cid = 0
for s in range(n):
    if seen[s]:
        continue          # уже в какой-то компоненте
    # обход (итеративный DFS) красит всю компоненту в цвет cid
    stack = [s]
    seen[s] = True
    while stack:
        u = stack.pop()
        comp_id[u] = cid
        for v in g[u]:
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    cid += 1              # компонента закрашена — увеличиваем счётчик

print("Число компонент:", cid)
print("Метки компонент:", comp_id)

Здесь три компоненты: {0,1,2}, {3,4}, {5,6}. Внешний цикл гарантирует, что мы запустим обход из каждой ещё не покрашенной вершины ровно один раз, поэтому счётчик cid в точности равен числу компонент. Сложность — O(n + m): каждая вершина и ребро обрабатываются единожды.

Вывод:

Число компонент: 3
Метки компонент: [0, 0, 0, 1, 1, 2, 2]

Классика: число островов на сетке

Самая популярная формулировка — «сколько островов?»: дана сетка из суши (#) и воды (.), острова — связные группы суши (по 4 направлениям). Сетка — это неявный граф: вершины — клетки суши, рёбра — соседство. Считаем компоненты тем же приёмом.

from collections import deque

grid = [
    "#.##",
    "#..#",
    "...#",
    "#.#.",
]
R, C = len(grid), len(grid[0])
visited = [[False] * C for _ in range(R)]
islands = 0
for i in range(R):
    for j in range(C):
        if grid[i][j] == "#" and not visited[i][j]:
            islands += 1               # нашли новый остров
            q = deque([(i, j)])        # заливаем его BFS-ом
            visited[i][j] = True
            while q:
                r, c = q.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "#" and not visited[nr][nc]:
                        visited[nr][nc] = True
                        q.append((nr, nc))
print("Островов:", islands)

Это та же «заливка» (flood fill), что в графике: нашли непокрашенную сушу — залили весь остров, увеличили счётчик. Сложность — O(R·C), каждая клетка посещается один раз.

Вывод:

Островов: 4

А если граф ориентированный?

В ориентированном графе понятие связности тоньше. Обычная «слабая» связность (если игнорировать направления) находится тем же обходом. Но «сильная» связность (когда из любой вершины достижима любая другая с учётом направлений) требует особых алгоритмов — компоненты сильной связности (SCC), например алгоритмы Косарайю или Тарьяна. Это уже продвинутая тема; для начала достаточно понимать, что в неориентированном графе всё решается простым обходом.

Подводные камни

Не сбрасывай seen между запусками — массив посещённых общий на весь граф.
На сетке аккуратно с границами: проверяй 0 <= nr < R и 0 <= nc < C перед обращением.
Диагонали. Уточняй: «острова» по 4 направлениям или по 8 (с диагоналями)? Это меняет ответ.
Рекурсивная заливка большой сетки переполнит стек — используй очередь/стек явно.

Итог

Компонента связности — максимальный достижимый «кусок» графа; граф распадается на компоненты.
Алгоритм: для каждой непосещённой вершины запустить обход; число запусков = число компонент; всё за O(n+m).
«Число островов» — та же задача о компонентах на сетке (flood fill).
В ориентированных графах сильная связность (SCC) требует отдельных алгоритмов.