17.1 Алгоритм Косараджу¶

Алгоритм Косараджу — это классический способ найти компоненты сильной связности в ориентированном графе.

Он особенно полезен в задачах, где нужно:

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

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

В ориентированном графе недостаточно того, что вершины просто связаны ребрами. Важно, можно ли пройти по направлению ребер из одной вершины в другую.

Говорят, что граф сильно связен, если из любой вершины можно добраться до любой другой.

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

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

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

Идея алгоритма¶

Алгоритм Косараджу делает два обхода DFS.

Первый обход¶

На первом проходе мы запускаем DFS по исходному графу и записываем вершины в список по времени выхода.

Это значит:

мы заходим в вершину;
обходим всех ее потомков;
только после этого добавляем вершину в порядок.

Именно этот порядок и является ключом ко всему алгоритму.

Второй обход¶

Затем мы:

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

Почему это работает интуитивно¶

Представим, что каждая компонента сильной связности — это один "суперузел". Тогда весь граф компонент — DAG.

Если в таком DAG есть ребро из компоненты A в компоненту B, то при DFS по исходному графу вершины из A обычно будут завершаться позже, чем вершины из B. Поэтому в порядке убывания времени выхода сначала окажутся вершины из "истоков" DAG компонент.

Когда мы переворачиваем ребра, направления между компонентами меняются. И если начать DFS с вершины правильной компоненты, обход уже не утечет в чужие части графа: он соберет ровно одну компоненту сильной связности.

Это и есть главный замысел алгоритма.

Небольшой пример¶

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

flowchart LR
    A((1)) --> B((2))
    B --> A
    B --> C((3))
    C --> D((4))
    D --> C
    D --> E((5))
    E --> F((6))
    F --> E

Hold "Ctrl" to enable pan & zoom

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

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

Потому что:

между 1 и 2 можно ходить в обе стороны;
между 3 и 4 тоже;
между 5 и 6 тоже;
а вот назад из {5,6} в {3,4} уже нельзя.

Сжатый граф компонент выглядит так:

flowchart LR
    C1[1, 2] --> C2[3, 4] --> C3[5, 6]

Hold "Ctrl" to enable pan & zoom

Это DAG.

Пошаговая схема работы¶

Шаг 1. Строим два графа¶

Нам нужны:

исходный граф g;
обратный граф gr, где все ребра перевернуты.

Если в исходном графе есть ребро u -> v, то:

в g добавляем v в список u;
в gr добавляем u в список v.

Шаг 2. Первый DFS¶

Обходим все вершины исходного графа.

Когда DFS полностью завершает работу с вершиной, добавляем ее в массив order.

Важно: вершина кладется в order после обхода всех ее исходящих ребер.

Шаг 3. Разворачиваем порядок¶

После первого прохода массив order хранит вершины в порядке возрастания времени выхода.

Для второго прохода идем по нему с конца к началу.

Шаг 4. Второй DFS¶

Теперь запускаем DFS по обратному графу gr.

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

Можно:

просто нумеровать компоненты;
сохранять список вершин каждой компоненты;
строить сжатый граф.

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

Ниже — удобная соревновательная реализация.

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

int n, m;
vector<vector<int>> g, gr;
vector<int> used, order, comp;
vector<vector<int>> components;

void dfs1(int v) {
    used[v] = 1;
    for (int to : g[v]) {
        if (!used[to]) dfs1(to);
    }
    order.push_back(v);
}

void dfs2(int v, int c) {
    comp[v] = c;
    components[c].push_back(v);
    for (int to : gr[v]) {
        if (comp[to] == -1) dfs2(to, c);
    }
}

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

    cin >> n >> m;
    g.assign(n + 1, {});
    gr.assign(n + 1, {});

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

    used.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        if (!used[v]) dfs1(v);
    }

    reverse(order.begin(), order.end());

    comp.assign(n + 1, -1);
    int cnt = 0;

    for (int v : order) {
        if (comp[v] == -1) {
            components.push_back({});
            dfs2(v, cnt);
            cnt++;
        }
    }

    cout << cnt << '\n';
    for (int i = 0; i < cnt; i++) {
        cout << "Компонента " << i + 1 << ": ";
        for (int v : components[i]) cout << v << ' ';
        cout << '\n';
    }

    return 0;
}

Что хранит эта программа¶

order — порядок вершин по убыванию времени выхода из первого DFS;
comp[v] — номер компоненты, которой принадлежит вершина v;
components[i] — список вершин i-й компоненты.

Асимптотика¶

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

O(n + m),

где:

n — число вершин;
m — число ребер.

Почему так:

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

Память тоже составляет O(n + m).

Как восстановить граф компонент¶

После того как известен массив comp, можно построить сжатый граф.

Идея очень простая:

если есть ребро u -> v;
и comp[u] != comp[v];
то в графе компонент есть ребро comp[u] -> comp[v].

Пример кода:

vector<set<int>> dag(cnt);
for (int u = 1; u <= n; u++) {
    for (int v : g[u]) {
        if (comp[u] != comp[v]) {
            dag[comp[u]].insert(comp[v]);
        }
    }
}

Использование set удобно, чтобы не добавлять одинаковые ребра много раз.

Типовые применения¶

1. Сжатие графа в DAG¶

Очень часто задача кажется сложной на исходном графе из-за циклов. Но после сжатия компонент сильной связности циклы исчезают, и можно применять:

топологическую сортировку;
динамическое программирование по DAG;
поиск максимального/минимального пути по компонентам.

2. Проверка сильной связности всего графа¶

Если после работы алгоритма получилась ровно одна компонента, то весь граф сильно связен.

3. 2-SAT¶

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

4. Анализ взаимной достижимости¶

Если две вершины попали в одну компоненту, то каждая достижима из другой.

Частые ошибки¶

Ошибка 1. Забыли перевернуть порядок¶

После первого DFS нужно идти по вершинам в обратном порядке массива order.

Если этого не сделать, компоненты найдутся неправильно.

Ошибка 2. Во втором DFS обходят не обратный граф¶

Первый DFS идет по g, второй — по gr.

Если оба обхода делать по одному и тому же графу, алгоритм сломается.

Ошибка 3. Путают момент добавления вершины в `order`¶

Вершину нужно добавлять после обхода детей, а не до.

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

Ошибка 4. Не запускают DFS из всех вершин¶

Граф может быть несвязным даже как ориентированный объект. Поэтому оба этапа должны учитывать все вершины.

Сравнение с алгоритмом Тарьяна¶

Есть еще один очень известный алгоритм поиска компонент сильной связности — алгоритм Тарьяна.

Разница такая:

Косараджу проще понять и проще реализовать с нуля;
Тарьян делает все за один DFS;
оба работают за O(n + m).

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

Еще один пример¶

Пусть даны ребра:

1 -> 2
2 -> 3
3 -> 1
3 -> 4
4 -> 5
5 -> 4
5 -> 6

Тогда компоненты:

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

Сжатый граф:

flowchart LR
    A[1, 2, 3] --> B[4, 5] --> C[6]

Hold "Ctrl" to enable pan & zoom

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

Практическая мысль для олимпиадника¶

Если в ориентированном графе спрашивают что-то вроде:

какие вершины эквивалентны по достижимости;
можно ли свести граф к ацикличному виду;
сколько "блоков" взаимной достижимости есть в графе;
как посчитать что-то по циклическим областям графа,

то почти наверняка стоит подумать о компонентах сильной связности.

А если нужно просто и надежно найти эти компоненты, алгоритм Косараджу — один из самых удобных инструментов.

Краткое резюме¶

Алгоритм Косараджу:

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

Главные плюсы:

простая идея;
реализация хорошо запоминается;
работает за O(n + m);
отлично подходит для сжатия графа в DAG.

17.1 Алгоритм Косараджу¶

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

Идея алгоритма¶

Первый обход¶

Второй обход¶

Почему это работает интуитивно¶

Небольшой пример¶

Пошаговая схема работы¶

Шаг 1. Строим два графа¶

Шаг 2. Первый DFS¶

Шаг 3. Разворачиваем порядок¶

Шаг 4. Второй DFS¶

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

Что хранит эта программа¶

Асимптотика¶

Как восстановить граф компонент¶

Типовые применения¶

1. Сжатие графа в DAG¶

2. Проверка сильной связности всего графа¶

3. 2-SAT¶

4. Анализ взаимной достижимости¶

Частые ошибки¶

Ошибка 1. Забыли перевернуть порядок¶

Ошибка 2. Во втором DFS обходят не обратный граф¶

Ошибка 3. Путают момент добавления вершины в order¶

Ошибка 4. Не запускают DFS из всех вершин¶

Сравнение с алгоритмом Тарьяна¶

Еще один пример¶

Практическая мысль для олимпиадника¶

Краткое резюме¶

Ошибка 3. Путают момент добавления вершины в `order`¶