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

Дан ориентированный граф. Нужно упорядочить вершины так, чтобы для каждого ребра $u \to v$ вершина $u$ стояла левее $v$.

Такой порядок называется топологическим. Он существует тогда и только тогда, когда в графе нет циклов: внутри цикла нельзя расставить вершины так, чтобы все рёбра смотрели вперёд.

Ориентированный граф без циклов называют DAG (directed acyclic graph). Это главный случай, где работает динамика на графе: состояния можно считать в топологическом порядке, и все зависимости к моменту вычисления уже готовы.

Через времена выхода

Ключевое наблюдение: если есть ребро $u \to v$, то $tout_u > tout_v$.

Два случая. Если к моменту просмотра ребра $v$ ещё не посещена — обход спустится в неё и выйдет раньше, чем из $u$. Если посещена и уже завершена — её $tout$ проставлен, а $tout_u$ ещё нет. Третий случай, «посещена и не завершена», означал бы обратное ребро, то есть цикл, — а его нет.

Значит, порядок по убыванию $tout$ и есть топологический.

Сортировать при этом не нужно: достаточно записывать вершины в момент выхода и в конце развернуть список.

vector<int> order;

void dfs(int v) {
    color[v] = 1;
    for (int to : g[v]) if (color[to] == 0) dfs(to);
    color[v] = 2;
    order.push_back(v);
}

// в main:
for (int v = 0; v < n; v++) if (color[v] == 0) dfs(v);
reverse(order.begin(), order.end());

Сложность — $O(n + m)$. Именно поэтому запись в момент выхода лучше сортировки: та добавила бы лишний логарифм ни за что.

Проверка на цикл встраивается прямо сюда — третьим цветом. Если встретили ребро в вершину цвета 1, топологического порядка не существует.

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

Через степени входа

Второй способ, алгоритм Кана, не использует рекурсию — и потому безопаснее при больших $n$.

Считаем для каждой вершины число входящих рёбер. Кладём в очередь все вершины с нулём. Достаём по одной, добавляем в ответ и уменьшаем счётчик у всех соседей; те, у кого счётчик обнулился, кладём в очередь.

vector<int> inDegree(n, 0);
for (int v = 0; v < n; v++) for (int to : g[v]) inDegree[to]++;

queue<int> q;
for (int v = 0; v < n; v++) if (inDegree[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]) if (--inDegree[to] == 0) q.push(to);
}

bool hasCycle = (int)order.size() < n;

Проверка на цикл получается бесплатно: если в ответе оказались не все вершины, значит остались те, чей счётчик так и не обнулился, — а это цикл.

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

Порядок не единственный

Топологических порядков обычно много. Для «ромба» $1 \to 2$, $1 \to 3$, $2 \to 4$, $3 \to 4$ подходят и $1,2,3,4$, и $1,3,2,4$.

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

Зачем это нужно

Динамика на DAG. Считаем что-нибудь для каждой вершины, зная значения для всех, куда из неё есть рёбра. Например, длиннейший путь: идём в обратном топологическом порядке, $dp_v = 1 + \max dp_{to}$. В графе с циклами эта задача NP-полна, в DAG — линейна.

Порядок задач. Классическая постановка «есть зависимости между делами, в каком порядке их выполнять». Ответ «невозможно» означает цикл в зависимостях.

Проверка на противоречивость. Даны отношения вида $a < b$; существует ли согласованный порядок? Это ровно наличие топологической сортировки.

Основа для конденсации. Граф компонент сильной связности — всегда DAG, и работать с ним удобно именно в топологическом порядке.