16.1 Топологическая сортировка¶

Топологическая сортировка — это один из базовых алгоритмов для ориентированных ациклических графов (DAG). Она позволяет расположить вершины в таком порядке, чтобы каждая дуга шла слева направо: если есть ребро u -> v, то вершина u должна стоять раньше v.

Это очень полезная идея во множестве задач:

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

Ниже мы разберём идею алгоритма, поймём, почему он работает, увидим, как обнаруживать цикл, и напишем реализации на C++.

Что такое топологическая сортировка¶

Пусть дан ориентированный граф. Требуется упорядочить его вершины так, чтобы для любого ребра u -> v вершина u находилась раньше v.

Это и есть топологический порядок.

Важно:

если граф ацикличен, топологическая сортировка существует;
если в графе есть цикл, топологической сортировки не существует.

Почему цикл всё ломает? Если есть цикл

a -> b -> c -> a,

то одновременно нужно, чтобы:

a стояла раньше b,
b раньше c,
c раньше a.

Это невозможно.

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

Рассмотрим граф зависимостей:

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

Один из возможных топологических порядков:

1, 2, 4, 3, 6, 5

Подойдёт и другой, например:

2, 1, 6, 4, 3, 5

Главное, чтобы все зависимости сохранялись.

Mermaid-схема¶

graph LR
    v1[1] --> v3[3]
    v2[2] --> v3
    v3 --> v5[5]
    v1 --> v4[4]
    v4 --> v5
    v2 --> v6[6]

Hold "Ctrl" to enable pan & zoom

Здесь нельзя ставить вершину 3 раньше 1 или 2, потому что в 3 ведут рёбра из них. Аналогично, 5 не может появиться раньше 3 и 4.

Главная интуиция¶

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

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

На этой идее основан алгоритм Кана.

Есть и другая точка зрения:

если делать DFS, то вершину удобно добавлять в ответ после обработки всех её потомков. Тогда в обратном порядке мы и получим корректную топологическую сортировку.

Способ 1. Топологическая сортировка через DFS¶

Это подход, который ближе к изложению в книге.

Идея¶

Запускаем обход в глубину из всех ещё не посещённых вершин.

Для каждой вершины храним состояние:

0 — не посещали;
1 — сейчас в стеке рекурсии;
2 — полностью обработали.

Когда DFS заходит в вершину, она получает состояние 1. Когда DFS завершает обработку всех исходящих рёбер, вершина получает состояние 2 и добавляется в массив ответа.

В конце нужно просто развернуть этот массив.

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

Если есть ребро u -> v, то при обходе:

либо v будет обработана раньше, чем завершится u,
либо v уже была обработана раньше.

То есть вершина u попадёт в список после v. Значит, после разворота списка u окажется раньше v.

Именно это нам и нужно.

Как обнаружить цикл¶

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

Это и есть обратное ребро, а значит — найден цикл.

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

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

int n, m;
vector<vector<int>> g;
vector<int> state;
vector<int> order;
bool has_cycle = false;

void dfs(int v) {
    state[v] = 1;
    for (int to : g[v]) {
        if (state[to] == 0) {
            dfs(to);
            if (has_cycle) return;
        } else if (state[to] == 1) {
            has_cycle = true;
            return;
        }
    }
    state[v] = 2;
    order.push_back(v);
}

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

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

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

    for (int v = 1; v <= n; v++) {
        if (state[v] == 0) {
            dfs(v);
            if (has_cycle) {
                cout << "IMPOSSIBLE\n";
                return 0;
            }
        }
    }

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

    for (int v : order) {
        cout << v << ' ';
    }
    cout << '\n';
}

Что делает этот код¶

Строит ориентированный граф.
Запускает DFS из каждой ещё не посещённой вершины.
Если находит переход в вершину цвета 1, сообщает, что есть цикл.
Иначе добавляет вершины в order по завершении обхода.
Разворачивает order и печатает ответ.

Сложность¶

Время: O(n + m)
Память: O(n + m)

Это оптимально для одной топологической сортировки.

Пошаговый разбор DFS-подхода¶

Пусть есть граф:

1 -> 2
2 -> 4
1 -> 3
3 -> 4

graph LR
    a1[1] --> a2[2]
    a1 --> a3[3]
    a2 --> a4[4]
    a3 --> a4

Hold "Ctrl" to enable pan & zoom

Запустим DFS из вершины 1.

Заходим в 1
Идём в 2
Из 2 идём в 4
У 4 нет исходящих рёбер, добавляем её в список
Возвращаемся, добавляем 2
Потом идём из 1 в 3
У 3 потомок 4 уже обработан
Добавляем 3
Добавляем 1

Получили список завершения:

4, 2, 3, 1

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

1, 3, 2, 4

Проверим:

1 раньше 2 — да
1 раньше 3 — да
2 раньше 4 — да
3 раньше 4 — да

Всё корректно.

Способ 2. Алгоритм Кана¶

На практике очень часто используют ещё один способ — через входные степени.

Идея¶

Для каждой вершины считаем количество входящих рёбер — indegree.

Все вершины с indegree = 0 можно поставить в начало.
Удаляем такую вершину из графа.
Уменьшаем входные степени её соседей.
Если у кого-то входная степень стала нулевой, добавляем его в очередь.

Так постепенно строится топологический порядок.

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

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

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

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

    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);

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

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) q.push(v);
    }

    vector<int> order;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        order.push_back(v);

        for (int to : g[v]) {
            indeg[to]--;
            if (indeg[to] == 0) {
                q.push(to);
            }
        }
    }

    if ((int)order.size() != n) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    for (int v : order) {
        cout << v << ' ';
    }
    cout << '\n';
}

Почему алгоритм Кана корректен¶

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

После удаления такой вершины новые вершины могут стать «готовыми» — то есть у них тоже входная степень станет нулевой.

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

Сложность¶

Время: O(n + m)
Память: O(n + m)

Какой способ лучше¶

Оба алгоритма линейные и очень полезные.

DFS удобно, когда¶

уже есть шаблон DFS;
нужно одновременно обнаруживать цикл через цвета;
дальше вы хотите делать что-то в стиле «обработать вершины в порядке выхода».

Алгоритм Кана удобно, когда¶

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

Когда топологическая сортировка существует¶

Только тогда, когда граф — DAG.

DAG — это Directed Acyclic Graph, то есть ориентированный граф без циклов.

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

Как проверить, что ответ действительно корректный¶

Если у вас уже есть массив pos, где pos[v] — позиция вершины v в топологическом порядке, то для каждого ребра u -> v должно выполняться:

pos[u] < pos[v]

Это простой способ проверить готовый ответ в отладке.

Типичные применения¶

1. Порядок изучения тем¶

Есть темы и зависимости вида: тему B можно изучать только после A. Тогда топологическая сортировка даёт корректный учебный порядок.

2. Сборка проекта¶

Если модуль parser использует lexer, то lexer должен быть собран раньше. Топологический порядок задаёт допустимую последовательность сборки.

3. Динамическое программирование по DAG¶

Если значение в вершине зависит только от её предков, то после топологической сортировки можно идти слева направо и корректно пересчитывать DP.

Например, так ищут:

число путей в DAG;
самый длинный путь в DAG;
кратчайший путь в DAG при подходящей постановке.

Пример задачи: вывести любой топологический порядок¶

Задача. Дан ориентированный граф из n вершин и m рёбер. Нужно вывести любой топологический порядок, а если его не существует, вывести IMPOSSIBLE.

Вход¶

В первой строке числа n и m. Далее идут m строк, каждая содержит ребро a b, означающее дугу a -> b.

Выход¶

любой корректный топологический порядок;
либо IMPOSSIBLE, если в графе есть цикл.

Пример¶

Вход:

Один из возможных выходов:

1 2 4 3 6 5

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

1. Путают ориентированный и неориентированный граф¶

Топологическая сортировка определена только для ориентированных графов.

2. Забывают запускать DFS из всех вершин¶

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

3. Неправильно понимают цикл в DFS¶

Переход в вершину состояния 2 — это нормально. Проблема только в переходе в вершину состояния 1.

4. Не разворачивают ответ в DFS-варианте¶

Если вершины добавляются после обработки всех потомков, в конце нужен reverse.

5. В алгоритме Кана забывают проверку размера ответа¶

Если удалось вывести меньше n вершин, значит, часть графа осталась внутри цикла.

Расширение: лексикографически минимальная топологическая сортировка¶

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

Тогда в алгоритме Кана вместо обычной очереди используют priority_queue с минимумом или set.

Код на C++¶

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

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

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

    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);

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

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) pq.push(v);
    }

    vector<int> order;

    while (!pq.empty()) {
        int v = pq.top();
        pq.pop();
        order.push_back(v);

        for (int to : g[v]) {
            indeg[to]--;
            if (indeg[to] == 0) {
                pq.push(to);
            }
        }
    }

    if ((int)order.size() != n) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    for (int v : order) {
        cout << v << ' ';
    }
    cout << '\n';
}

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

Что важно запомнить¶

Топологическая сортировка существует только в DAG.
Если в ориентированном графе есть цикл, корректного порядка нет.
Топологическую сортировку можно найти двумя основными способами:
через DFS и порядок выхода;
через алгоритм Кана и входные степени.
Оба метода работают за O(n + m).
Это один из ключевых инструментов для задач на зависимости и DP по графу.

Итого¶

Топологическая сортировка — это способ выстроить вершины DAG в правильном порядке зависимостей. Для олимпиадного программирования это один из фундаментальных алгоритмов: он не только сам по себе часто встречается в задачах, но и служит основой для множества более сложных решений, особенно в ориентированных ациклических графах.

Если ты видишь в задаче фразы вроде:

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

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