17.3 Алгоритм Тарьяна¶

Алгоритм Тарьяна — это линейный алгоритм поиска компонент сильной связности в ориентированном графе. В отличие от алгоритма Косараджу, где обычно делают два обхода графа и отдельно строят обратный граф, алгоритм Тарьяна находит все компоненты сильной связности за один DFS. Это делает его особенно удобным в задачах, где хочется получить компактную реализацию и не хранить транспонированный граф.

Что такое компонента сильной связности¶

Напомним определение. В ориентированном графе множество вершин образует компоненту сильной связности, если для любых двух вершин u и v из этого множества:

из u можно добраться в v,
и из v можно добраться в u.

То есть внутри такой компоненты каждая вершина достижима из каждой.

Например, если есть рёбра:

1 → 2
2 → 3
3 → 1
3 → 4
4 → 5
5 → 4

то здесь компоненты сильной связности такие:

{1, 2, 3}
{4, 5}

Потому что внутри тройки {1,2,3} можно ходить по циклу в обе стороны по достижимости, а вершины 4 и 5 тоже взаимно достижимы.

Зачем нужен алгоритм Тарьяна¶

Поиск SCC — это не просто отдельная техника. Он часто используется как строительный блок:

в задачах на сжатие графа в DAG компонент;
в задачах на анализ циклических зависимостей;
в задачах на 2SAT;
в задачах, где нужно понять, какие вершины «склеиваются» в сильно связанные блоки;
в задачах на графы состояний.

После сжатия каждой компоненты в одну вершину мы получаем ациклический граф компонент. Это очень полезно, потому что на DAG уже можно делать топологическую сортировку, динамику и другие стандартные приёмы.

Главная идея алгоритма¶

Алгоритм Тарьяна делает один обход DFS и для каждой вершины хранит два числа:

tin[v] — время входа в вершину v;
low[v] — минимальное время входа вершины, до которой можно добраться:
из v,
двигаясь по рёбрам DFS вниз,
и, возможно, одним обратным ребром в вершину, которая всё ещё находится в текущем стеке.

Интуитивно:

tin[v] говорит, когда мы впервые увидели вершину;
low[v] говорит, насколько высоко вверх по текущему DFS-дереву можно вернуться из поддерева вершины v.

Если в некоторый момент оказывается, что

low[v] = tin[v],

то вершина v является корнем компоненты сильной связности. Это означает, что из её поддерева уже нельзя подняться к более ранней вершине, которая ещё находится в той же незавершённой части обхода. Значит, все вершины на вершине стека до v образуют одну SCC.

Почему нужен стек¶

Во время DFS алгоритм кладёт вершины в стек. В стеке находятся те вершины, которые:

уже посещены,
но их компонента сильной связности ещё не выделена окончательно.

Когда мы понимаем, что нашли корень SCC, мы начинаем вынимать вершины из стека, пока не вынем саму вершину-корень. Все снятые вершины и есть одна компонента.

Это очень важный момент:

не каждая посещённая вершина остаётся «актуальной» навсегда;
только вершины, которые всё ещё лежат в стеке, могут участвовать в текущей незавершённой компоненте.

Именно поэтому в алгоритме обычно есть массив in_stack[v].

Наглядный пример¶

Рассмотрим граф:

1 → 2
2 → 3
3 → 1
3 → 4
4 → 5
5 → 4
5 → 6

Тогда компоненты сильной связности будут:

{1,2,3}
{4,5}
{6}

Схема графа:

graph LR
    A1[1] --> A2[2]
    A2 --> A3[3]
    A3 --> A1
    A3 --> A4[4]
    A4 --> A5[5]
    A5 --> A4
    A5 --> A6[6]

Hold "Ctrl" to enable pan & zoom

Представим, что DFS стартует из вершины 1.

Шаг 1. Идём по циклу `1 → 2 → 3 → 1`¶

При входе во вершины получаем, например:

tin[1] = 0
tin[2] = 1
tin[3] = 2

Из 3 есть ребро в 1, а 1 всё ещё лежит в стеке. Значит, можно обновить:

low[3] = min(low[3], tin[1]) = 0

Потом это значение поднимется вверх:

low[2] = min(low[2], low[3]) = 0
low[1] = min(low[1], low[2]) = 0

Шаг 2. Идём дальше в `4` и `5`¶

Из 3 идём в 4, затем в 5.

tin[4] = 3
tin[5] = 4

Из 5 есть ребро обратно в 4, а 4 лежит в стеке. Значит:

low[5] = min(low[5], tin[4]) = 3

После возврата:

low[4] = min(low[4], low[5]) = 3

Раз low[4] = tin[4], то вершина 4 — корень SCC. Из стека снимутся 5, затем 4, и получится компонента {4,5}.

Шаг 3. Вершина `6`¶

Из 5 есть ребро в 6.

tin[6] = 5
у 6 нет пути назад к вершинам в стеке,
значит low[6] = tin[6]

Следовательно, {6} — отдельная компонента.

Шаг 4. Возврат к вершине `1`¶

После завершения поддерева 3 имеем:

low[1] = 0
tin[1] = 0

Значит, 1 — корень SCC, и со стека снимутся 3, 2, 1. Получим компоненту {1,2,3}.

Как обновляется `low[v]`¶

Это центральная часть алгоритма. При обходе рёбер из v в to бывают три случая.

1. Вершина `to` ещё не посещена¶

Тогда это обычное ребро дерева DFS. Мы идём в to, а после возврата делаем:

low[v] = min(low[v], low[to])

Почему так? Потому что всё, куда можно «подняться вверх» из поддерева to, потенциально достижимо и из v.

2. Вершина `to` уже посещена и лежит в стеке¶

Тогда найдено ребро в текущую незавершённую часть DFS. Это важное ребро, и делаем:

low[v] = min(low[v], tin[to])

Именно такие рёбра позволяют понять, что несколько вершин принадлежат одной SCC.

3. Вершина `to` уже посещена, но не лежит в стеке¶

Тогда её компонента уже выделена и завершена. Такое ребро не должно влиять на текущую SCC, поэтому его просто игнорируют при обновлении low.

Это одно из самых важных мест, где часто ошибаются в реализации.

Почему условие `low[v] = tin[v]` означает корень SCC¶

Поясним интуитивно.

Если low[v] < tin[v], это значит, что из поддерева v можно добраться до какой-то более ранней вершины, которая всё ещё находится в стеке. Значит, v не является верхней границей своей компоненты: компонента уходит выше.

Если же low[v] = tin[v], то выше подняться уже нельзя. Значит, вершина v — самая верхняя вершина своей SCC в текущем DFS, и все вершины стека от вершины сверху до v входят в одну и ту же компоненту.

Пошаговый шаблон алгоритма¶

Запускаем DFS из всех непосещённых вершин.
При входе в вершину:
назначаем tin[v] и low[v];
кладём вершину в стек;
отмечаем in_stack[v] = true.
Просматриваем все исходящие рёбра.
Если сосед не посещён — идём в DFS.
Если сосед в стеке — обновляем low.
После обработки всех соседей проверяем:
если low[v] = tin[v], то снимаем со стека вершины до v и формируем одну SCC.

Реализация на C++¶

Ниже — удобная и стандартная реализация алгоритма Тарьяна для поиска всех компонент сильной связности.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<int> tin, low, comp, st;
vector<bool> in_stack;
int timer = 0;
int comp_cnt = 0;

void dfs(int v) {
    tin[v] = low[v] = timer++;
    st.push_back(v);
    in_stack[v] = true;

    for (int to : g[v]) {
        if (tin[to] == -1) {
            dfs(to);
            low[v] = min(low[v], low[to]);
        } else if (in_stack[to]) {
            low[v] = min(low[v], tin[to]);
        }
    }

    if (low[v] == tin[v]) {
        while (true) {
            int u = st.back();
            st.pop_back();
            in_stack[u] = false;
            comp[u] = comp_cnt;
            if (u == v) break;
        }
        comp_cnt++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

    tin.assign(n + 1, -1);
    low.assign(n + 1, -1);
    comp.assign(n + 1, -1);
    in_stack.assign(n + 1, false);

    for (int v = 1; v <= n; v++) {
        if (tin[v] == -1) dfs(v);
    }

    cout << comp_cnt << '\n';
    for (int v = 1; v <= n; v++) {
        cout << v << " -> " << comp[v] << '\n';
    }

    return 0;
}

Что хранит эта реализация¶

tin[v] — время входа;
low[v] — минимальное достижимое время входа внутри текущего DFS-стека;
st — стек вершин;
in_stack[v] — лежит ли вершина в стеке сейчас;
comp[v] — номер компоненты сильной связности вершины v.

Разбор кода¶

Инициализация вершины¶

Строка

tin[v] = low[v] = timer++;

означает, что при первом входе в вершину её номер времени входа и начальное low совпадают.

Обработка непосещённого соседа¶

Если to ещё не посещён, запускаем dfs(to), а затем пытаемся протащить значение low[to] вверх:

low[v] = min(low[v], low[to]);

Обработка ребра в стек¶

Если сосед уже посещён и всё ещё находится в стеке, значит мы нашли путь назад в текущую открытую компоненту:

low[v] = min(low[v], tin[to]);

Выделение компоненты¶

Если low[v] == tin[v], то v — корень SCC. Тогда снимаем вершины со стека, пока не дойдём до v.

Пример входных данных¶

Один из возможных результатов:

компонент 0: {6}
компонент 1: {4,5}
компонент 2: {1,2,3}

Номера компонент могут отличаться — это нормально. Важно только само разбиение на SCC.

Восстановление списка вершин каждой компоненты¶

Часто в задачах хочется не только номер компоненты для каждой вершины, но и сам список вершин внутри каждой SCC.

Тогда после работы алгоритма можно сделать так:

vector<vector<int>> components(comp_cnt);
for (int v = 1; v <= n; v++) {
    components[comp[v]].push_back(v);
}

После этого components[c] будет содержать все вершины компоненты c.

Построение графа компонент¶

После поиска SCC часто строят конденсацию графа — новый граф, где каждая компонента сжимается в одну вершину.

Если есть ребро u → v и comp[u] != comp[v], то в графе компонент появляется ребро

comp[u] → comp[v].

Этот граф всегда является DAG. Это фундаментальный факт: если бы в графе компонент был цикл, то все вершины этого цикла можно было бы объединить в одну большую SCC.

Пример кода:

vector<vector<int>> dag(comp_cnt);
set<pair<int,int>> used;

for (int u = 1; u <= n; u++) {
    for (int v : g[u]) {
        if (comp[u] != comp[v]) {
            if (!used.count({comp[u], comp[v]})) {
                used.insert({comp[u], comp[v]});
                dag[comp[u]].push_back(comp[v]);
            }
        }
    }
}

Сравнение с алгоритмом Косараджу¶

Оба алгоритма работают за O(n + m).

Косараджу¶

Плюсы:

проще понять на первом знакомстве;
идея очень наглядная: порядок выхода + обход обратного графа.

Минусы:

нужен второй обход;
обычно нужно хранить обратный граф.

Тарьян¶

Плюсы:

один DFS;
не нужен транспонированный граф;
часто удобен как библиотечная реализация.

Минусы:

сложнее интуитивно;
чаще возникают ошибки в low и в логике стека.

На практике полезно уметь писать оба алгоритма.

Типичные ошибки¶

Ошибка 1. Обновлять `low[v]` через `low[to]` для вершины, которая уже посещена¶

Если to уже посещена, и мы не пошли в неё рекурсивно, то при наличии ребра в стек надо делать именно:

low[v] = min(low[v], tin[to])

а не через low[to].

Ошибка 2. Не проверять `in_stack[to]`¶

Если обновлять low по любой посещённой вершине, алгоритм начнёт склеивать лишние компоненты.

Ошибка 3. Забыть снять вершины из стека¶

Когда SCC найдена, все её вершины нужно обязательно убрать из стека и снять флаг in_stack.

Ошибка 4. Запускать DFS только из одной вершины¶

Граф может быть несвязным по достижимости, поэтому надо запускать DFS из всех вершин, где tin[v] == -1.

Оценка сложности¶

Алгоритм работает за

O(n + m) по времени;
O(n) дополнительной памяти, не считая самого графа.

Почему время линейное:

каждая вершина входит в DFS один раз;
каждое ребро просматривается один раз;
каждая вершина кладётся в стек и снимается со стека ровно один раз.

Где особенно полезен алгоритм Тарьяна¶

2SAT — можно находить SCC графа импликаций.
Сжатие графа — когда нужно превратить произвольный ориентированный граф в DAG компонент.
Анализ зависимостей — например, в графе модулей или состояний.
Поиск циклических блоков — когда важно понять, какие вершины образуют взаимно достижимые группы.

Упрощённая интуиция для запоминания¶

Можно запомнить алгоритм Тарьяна так:

DFS идёт вниз по графу;
стек хранит текущую «живую» область обхода;
low[v] показывает, можно ли из поддерева v вернуться выше;
если вернуться выше нельзя, то мы закрываем одну компоненту.

То есть алгоритм всё время отвечает на вопрос:

«Эта часть DFS ещё соединена с чем-то выше, или уже пора выделить готовую SCC?»

Небольшое упражнение¶

Попробуйте вручную запустить алгоритм Тарьяна на графе:

1 → 2
2 → 1
2 → 3
3 → 4
4 → 5
5 → 3
5 → 6

Подумайте:

какие будут SCC;
в каком порядке они снимутся со стека;
какие значения low получат вершины 2, 3 и 5.

Правильный ответ:

{1,2}
{3,4,5}
{6}

Но особенно полезно именно пройти алгоритм руками.

Итоги¶

Алгоритм Тарьяна — один из важнейших алгоритмов для ориентированных графов.

Он позволяет:

находить компоненты сильной связности за линейное время;
делать это одним DFS;
сразу получать основу для построения конденсации графа.

Если алгоритм Косараджу удобно понимать как метод через два обхода, то алгоритм Тарьяна удобнее воспринимать как DFS со стеком и умением определить момент, когда компонента полностью замкнулась.