Компоненты сильной связности
Группируйте взаимно достижимые вершины с помощью Тарьяна
«Компоненты сильной связности» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое SCC
Сильносвязная компонента — это максимальная группа вершин, в которой из каждой вершины можно попасть в любую другую, следуя по ориентированным рёбрам.
Зачем это нужно
Объединение каждой SCC в одну сверхвершину превращает любой ориентированный граф в DAG. Так взаимные зависимости становится проще анализировать.
Тарьян за один проход
Алгоритм Тарьяна находит все SCC за один DFS. Он работает за O(V + E) — столько же стоит один обычный обход.
Номера обнаружения
Назначьте каждой вершине время обнаружения в порядке, в котором DFS впервые посещает её. Эти идентификаторы позволяют сравнить, какая вершина была посещена раньше.
disc = [-1] * n
timer = 0Значение нижней ссылки
Значение нижней ссылки вершины — это наименьший идентификатор обнаружения, достижимый из неё, в том числе через обратные рёбра. Оно задаёт опорную точку компоненты.
low = [-1] * nПоместите вершину в стек
Когда DFS входит в вершину, установите её disc и low, затем поместите её в стек вершин, которые могут принадлежать одной компоненте.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueОбновите low по дочерним вершинам
После рекурсивной обработки непосещённого потомка подтяните его значение low: low[u] становится минимумом своего значения и значения low потомка.
dfs(v)
low[u] = min(low[u], low[v])Обработайте обратные рёбра
Если сосед уже находится в стеке, он является предком в этой SCC. Используйте его disc, чтобы уменьшить low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Найдите корень компоненты
Когда low[u] равно disc[u], вершина u является корнем SCC. Все вершины выше неё в стеке принадлежат одной компоненте.
Извлеките компоненту
В корне вызывайте pop, извлекая вершины из стека, пока не удалите u. Извлечённая группа и есть одна сильносвязная компонента.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakКосараджу как альтернатива
Предпочитаете два прохода? Алгоритм Косараджу выполняет DFS, разворачивает каждое ребро, а затем снова выполняет DFS в порядке завершения, выделяя SCC.
Быстрая проверка
Во время DFS алгоритма Тарьяна для вершины u выполняется условие low[u] == disc[u]. Что это означает?
Итоги: SCC с алгоритмом Тарьяна
Отслеживайте disc и low за один DFS, храните активные вершины в стеке и извлекайте компоненту всякий раз, когда low равно disc. SCC за O(V+E). 🧩
Часто задаваемые вопросы
Урок «Компоненты сильной связности» бесплатный?
Да — полный текст урока «Компоненты сильной связности» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Компоненты сильной связности»?
Группируйте взаимно достижимые вершины с помощью Тарьяна Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Компоненты сильной связности»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Топологическая сортировка алгоритмом Кана
- Поиск циклов в ориентированных графах
- Компоненты сильной связности
- Мосты и точки сочленения