Единственность топологической сортировки

Топологических сортировок у графа обычно много. Когда она ровно одна?

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

Доказательство

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

Если где-то ребра нет — сортировок несколько. Пусть между соседними $x$ и $y$ ребра нет. Поменяем их местами.

Что могло сломаться? Рёбра, выходящие из $x$, вели во что-то правее $y$ — и продолжают вести вправо. Рёбра, входящие в $x$, шли из чего-то левее — и продолжают. То же для $y$. Единственная пара, которая могла бы пострадать, — сами $x$ и $y$, но между ними ребра нет.

Значит, получился другой корректный порядок. $\blacksquare$

Проверка

vector<int> order = topsort();
if (order.empty()) { /* есть цикл, сортировки нет вовсе */ }
bool unique = true;
for (int i = 0; i + 1 < n; i++)
    if (!hasEdge(order[i], order[i + 1])) unique = false;

Построение сортировки — $O(n + m)$, проверка — $n-1$ вопрос «есть ли ребро». Если рёбра лежат в set<pair<int,int>>, это $O(n \log m)$; если хранить их в хеш-таблице — $O(n)$.

Проверено: на 60 000 случайных графов критерий совпал с подсчётом всех топологических сортировок перебором перестановок.

На что это похоже

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

Отсюда практическое следствие: если задача просит проверить, задают ли известные отношения полный порядок (например, «известны результаты матчей, можно ли однозначно проранжировать команды»), это ровно проверка единственности топсорта.