Topological Sort

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

Топологическая сортировка — это такой порядок вершин в ориентированном графе, что каждое ребро идет слева направо.

Если есть ребро:

a → b

Тогда в топологическом порядке вершина a должна стоять раньше вершины b.

Топологическая сортировка существует только в ориентированном графе без циклов. Такой граф называется DAG.

Что такое DAG?

DAG — это Directed Acyclic Graph.

По-русски:

ориентированный ациклический граф

То есть:

ребра имеют направление
в графе нет циклов

Пример

Пусть есть зависимости:

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

Один правильный топологический порядок:

1 2 3 4

Другой правильный порядок:

1 3 2 4

Оба варианта правильные, потому что 1 идет раньше 2 и 3, а 2 и 3 идут раньше 4.

Где используется?

задачи с зависимостями
порядок выполнения дел
расписание курсов
компиляция файлов
проверка, есть ли цикл в ориентированном графе
DP по DAG

Метод 1: через DFS

Идея простая:

запускаем DFS
сначала обходим всех потомков
потом добавляем вершину в ответ
в конце разворачиваем ответ

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

DFS-шаблон

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }

    ans.push_back(v);
}

После всех DFS:

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

Задача 1: найти топологический порядок

Дан ориентированный ациклический граф. Нужно вывести один топологический порядок.

Input

Output

1 3 2 4

Ответ может быть не единственный.

Полная реализация через DFS

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

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
vector<int> ans;

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }

    ans.push_back(v);
}

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

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }

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

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

Проблема DFS-версии

Обычная DFS-версия просто строит порядок. Но если в графе есть цикл, топологической сортировки не существует.

Поэтому лучше уметь проверять цикл.

если есть цикл → topsort невозможен
если цикла нет → topsort существует

Проверка цикла через цвета

Используем массив color:

0 — вершина еще не посещена
1 — сейчас находимся внутри DFS этой вершины
2 — вершина полностью обработана

Если из вершины v мы идем в вершину to, у которой color[to] == 1, значит нашли цикл.

DFS с проверкой цикла

bool hasCycle = false;

void dfs(int v) {
    color[v] = 1;

    for (int to : g[v]) {
        if (color[to] == 0) {
            dfs(to);
        } else if (color[to] == 1) {
            hasCycle = true;
        }
    }

    color[v] = 2;
    ans.push_back(v);
}

Полная реализация с проверкой цикла

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

const int N = 100010;

int n, m;
vector<int> g[N];
int color[N];
vector<int> ans;
bool hasCycle = false;

void dfs(int v) {
    color[v] = 1;

    for (int to : g[v]) {
        if (color[to] == 0) {
            dfs(to);
        } else if (color[to] == 1) {
            hasCycle = true;
        }
    }

    color[v] = 2;
    ans.push_back(v);
}

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

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        if (color[i] == 0) {
            dfs(i);
        }
    }

    if (hasCycle) {
        cout << -1;
        return 0;
    }

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

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

Метод 2: алгоритм Кана

Второй способ — через входящие степени. Он называется Kahn algorithm.

Входящая степень вершины — это сколько ребер входит в вершину.

indeg[v]

Если indeg[v] == 0, значит перед этой вершиной нет зависимостей. Ее можно поставить в ответ.

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

считаем indeg для всех вершин
кладем в queue все вершины с indeg = 0
достаем вершину из queue
добавляем ее в answer
уменьшаем indeg у ее соседей
если у соседа indeg стал 0, кладем его в queue

Код идеи

queue<int> q;

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

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

    ans.push_back(v);

    for (int to : g[v]) {
        indeg[to]--;

        if (indeg[to] == 0) {
            q.push(to);
        }
    }
}

Как понять, что есть цикл?

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

if (ans.size() != n) {
    cout << -1;
}

Почему? Потому что в цикле нет вершины, у которой можно нормально удалить все зависимости.

Полная реализация алгоритма Кана

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

const int N = 100010;

int n, m;
vector<int> g[N];
int indeg[N];
vector<int> ans;

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

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        indeg[b]++;
    }

    queue<int> q;

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

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

        ans.push_back(v);

        for (int to : g[v]) {
            indeg[to]--;

            if (indeg[to] == 0) {
                q.push(to);
            }
        }
    }

    if ((int)ans.size() != n) {
        cout << -1;
        return 0;
    }

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

Лексикографически минимальный topsort

Иногда нужно вывести минимальный порядок. Тогда вместо queue используем priority_queue как min-heap.

priority_queue<int, vector<int>, greater<int>> q;

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

Реализация минимального topsort

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

const int N = 100010;

int n, m;
vector<int> g[N];
int indeg[N];
vector<int> ans;

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

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        indeg[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> q;

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

    while (!q.empty()) {
        int v = q.top();
        q.pop();

        ans.push_back(v);

        for (int to : g[v]) {
            indeg[to]--;

            if (indeg[to] == 0) {
                q.push(to);
            }
        }
    }

    if ((int)ans.size() != n) {
        cout << -1;
        return 0;
    }

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}

DFS vs Kahn

Метод	Идея	Плюс
DFS	добавляем вершину после обхода потомков	короткий код
Kahn	удаляем вершины с indeg = 0	удобно искать цикл и минимальный порядок

Асимптотика

Метод	Время	Память
DFS	O(n + m)	O(n + m)
Kahn с queue	O(n + m)	O(n + m)
Kahn с priority_queue	O((n + m) log n)	O(n + m)

Короткий шаблон

queue<int> q;

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

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

    ans.push_back(v);

    for (int to : g[v]) {
        indeg[to]--;

        if (indeg[to] == 0) {
            q.push(to);
        }
    }
}

if ((int)ans.size() != n) {
    cout << -1;
} else {
    for (int x : ans) {
        cout << x << ' ';
    }
}