Strongly Connected Components
В ориентированном графе есть n узлов, пронумерованных от 0 до n-1, и список edges, где [from, to] — это ребро из узла from в узел to.
Сильно связная компонента — это наибольшая группа узлов, в которой из каждого узла можно попасть в любой другой, следуя по рёбрам. Каждый узел принадлежит ровно одной компоненте, а узел, не входящий ни в один цикл, образует компоненту сам по себе. Верните количество сильно связных компонент.
Функция
- ninteger
- количество узлов
- edgesinteger-2d-array
- ориентированные рёбра, каждое в формате [from, to]
- Возвращаетinteger
- количество сильно связных компонент
Ограничения
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to], где0 ≤ from, to < nиfrom ≠ to- Ни одно ребро не встречается дважды.
Примеры
- Ввод
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Вывод
- 3
- Пояснение
- Узлы 0, 1 и 2 образуют цикл, поэтому каждый из них достижим из остальных. Узлы 3 и 4 указывают друг на друга. Из узла 5 можно достичь узла 4, но обратно к узлу 5 пути нет, поэтому он образует отдельную компоненту: всего 3 компоненты.
- Ввод
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Вывод
- 4
- Пояснение
- Узлы 0 и 1 указывают друг на друга и образуют одну компоненту. Ребро от 2 к 3 направлено только в одну сторону, поэтому 2 и 3 являются отдельными компонентами, а у узла 4 вообще нет рёбер: всего 4 компоненты.
Дополнительный вопрос
Сколько минимум рёбер нужно добавить, чтобы весь граф стал одной сильно связной компонентой?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Два узла принадлежат одной компоненте тогда и только тогда, когда каждый из них может достичь другого. Это можно проверить поиском из каждого узла, но при этом одни и те же рёбра проходятся снова и снова. Что один поиск в глубину может рассказать о том, где начинается компонента?
Пронумеруй узлы в порядке, в котором поиск в глубину впервые достигает их. Для каждого узла также отслеживай
low: наименьший номер узла, до которого можно добраться, спускаясь по дереву поиска, а затем проходя по одному ребру обратно к узлу, компонента которого всё ещё открыта. Узел, у которого значениеlowравно его собственному номеру, — первый узел своей компоненты.Храните посещённые узлы в стеке. Когда обход узла завершается и
lowравен номеру этого узла, извлеките из стека все узлы до него: эти узлы образуют одну компоненту, поэтому увеличьте счётчик. В одном из тестов глубина поиска достигает 5000 узлов, поэтому используйте собственный стек кадров (узел, следующее ребро) вместо рекурсии.
Решение
Сожмите каждую компоненту в точку, и компоненты образуют граф без циклов. Алгоритмы Косарайю и Тарьяна используют это, чтобы найти каждую компоненту за O(n + E), где E — количество рёбер.
Поиск вперёд и назад от каждого узла
Верно, но не успевает на самых больших тестах
Идея
Узлы u и v принадлежат одной компоненте тогда и только тогда, когда каждый из них может достичь другого. Поэтому для узла s, который пока не принадлежит ни одной компоненте, выполните поиск вперёд по рёбрам и назад по обратным рёбрам. Узлы, найденные обоими поисками, образуют его компоненту. В первом примере поиск вперёд из 0 находит узлы от 0 до 4, а поиск назад — 0, 1 и 2, поэтому {0, 1, 2} образуют одну компоненту.
Для каждой компоненты требуются два поиска по большей части графа. В цепочке из 5000 рёбер и 5001 узла каждый узел образует собственную компоненту, а поиски посещают около 2.5 × 10^7 узлов.
Алгоритм
- Постройте списки исходящих и входящих рёбер для каждой вершины.
- Возьмите следующую вершину
sбез компоненты и посчитайте новую компоненту. - Отметьте вершины, до которых можно добраться из
sпо исходящим рёбрам, и вершины, из которых можно добраться до неё по входящим рёбрам. - Каждая вершина, отмеченная обоими поисками, входит в компоненту
s. Когда у каждой вершины будет компонента, верните их количество.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countАлгоритм Косарайю: два прохода
Идея
В графе компонент одна из компонент является стоком: из неё не выходит ни одного ребра, и поиск, начатый внутри неё, находит ровно эту компоненту. Алгоритм Косарайю упорядочивает поиски так, чтобы каждый из них вёл себя именно так.
На первом проходе записывается каждая вершина в момент завершения поиска в глубину из неё. На втором проходе выполняется поиск в обращённом графе, в котором компоненты остаются теми же, начиная с вершины, завершившейся последней. Если ребро ведёт из компоненты B в компоненту C, то поиск в глубину из последней вершины B завершается после того, как завершится поиск по всем вершинам C. Поэтому, когда второй проход достигает C, все компоненты, из которых в C ведут рёбра, уже отнесены к компонентам, а поиск в обращённом графе не может покинуть C.
В первом примере вершины завершаются в порядке 4, 3, 2, 1, 0, 5. На втором проходе получаются {5}, затем {0, 1, 2}, затем {3, 4}.
Алгоритм
- Постройте списки исходящих и входящих рёбер.
- Запустите итеративный поиск в глубину из каждой непосещённой вершины и добавляйте каждую вершину в
orderпо завершении её обхода. - Пройдите по
orderс конца. Для каждой вершины, не входящей в компоненту, увеличьте счётчик на единицу и выполните поиск из неё по входящим рёбрам, присваивая компоненту каждой достигнутой вершине, которой она ещё не присвоена. Верните счётчик.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countАлгоритм Тарьяна: один проход со значениями low
Идея
Выполни один поиск в глубину и пронумеруй каждую вершину в порядке её посещения: это её index. Поддерживай стек посещённых вершин, компоненты которых ещё не закрыты, и значение low: наименьший индекс вершины, до которой можно добраться, спустившись по дереву поиска, а затем пройдя по одному ребру назад к вершине в этом стеке.
Когда обработка вершины завершается и её low меньше index, значит, что-то ниже по дереву поднимается обратно к более ранней незакрытой вершине, поэтому эта вершина остаётся в стеке. Если значения равны, вершина — первая, которую поиск посетил в её компоненте: снимай вершины со стека до неё включительно и считай одну компоненту. Ребро к уже извлечённой вершине ведёт в завершённую компоненту, из которой нельзя вернуться, поэтому его игнорируют.
В первом примере вершина 3 извлекает {4, 3}, а вершина 0 — {2, 1, 0}. Ребро вершины 5 ведёт к уже извлечённой вершине 4, поэтому вершина 5 извлекается отдельно.
Алгоритм
- Для каждого непосещённого узла присвой ему следующий индекс, установи
lowравным тому же значению, добавь его в стек узлов и добавь кадр (node, first edge). - Если у узла в верхнем кадре остались рёбра, пройди по одному из них: непосещённой целевой вершине присвой индекс и добавь кадр, а если целевая вершина находится в стеке узлов, уменьши
low[node]до её индекса. - В противном случае сними кадр и уменьши
lowродительского узла доlow[node]. Еслиlow[node]равноindex[node], снимай узлы со стека узлов, пока не дойдёшь до этого узла, и засчитай компоненту.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Ловушки и крайние случаи
- Забывать о вершинах без рёбер. Во втором примере вершина 4 не входит ни в одно ребро и всё равно является компонентой.
- Уменьшать
lowчерез любую посещённую вершину, а не только через вершины в стеке. В первом примере ребро5 → 4тогда не даёт вершине 5 закрыть свою компоненту. - Считать, что рёбра направлены в обе стороны. Так находятся компоненты связности: в первом примере получилось бы 1 вместо 3.
- Использовать рекурсию в Python. Цикл из 5000 вершин создаёт 5000 вложенных вызовов — в пять раз больше стандартного ограничения в 1000. Используйте собственный стек кадров.
- Выполнять второй проход алгоритма Косарайю по исходным рёбрам или в порядке первого посещения вершин. И то и другое объединяет компоненты, которые достигают друг друга только в одном направлении.
Частые вопросы3
Какова временная сложность поиска сильно связных компонент?
Время O(n + E) при использовании алгоритма Косарайю или Тарьяна, поскольку каждый узел и каждое ребро обрабатываются постоянное число раз. Оба алгоритма используют O(n + E) памяти для списков рёбер и стеков поиска.
Стоит ли использовать алгоритм Косарайю или алгоритм Тарьяна?
Алгоритм Косарайю — это два простых обхода, и в нём сложнее ошибиться. Алгоритму Тарьяна нужен один обход и не нужен обращённый граф, но приходится вести учёт low.
В чём разница между сильно связными компонентами и связными компонентами?
Связные компоненты не учитывают направление рёбер: два узла находятся в одной компоненте, если их соединяет какой-либо путь. В сильно связных компонентах каждый узел должен иметь возможность достичь другого. Первый пример — это одна связная компонента, но три сильно связные компоненты.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def countSCC(n, edges):
# Напишите код здесьТест #1
Тест #2
Аргументы
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Ожидаемый вывод
3