Топологическая сортировка (алгоритм Кана)

O(V+E)

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

Сигналы

задача должна идти перед другойпорядок, соблюдающий зависимостиобнаружить цикл в предпосылкахпорядок сборки / расписание курсов / порядок установкиориентированный граф, X должен произойти перед Y

Шаблон

function topoSort(n, adj) {
    const indeg = new Array(n).fill(0);
    for (const u in adj) for (const v of adj[u]) indeg[v]++;
    const queue = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order = [];
    while (queue.length) {
        const u = queue.shift();
        order.push(u);
        for (const v of adj[u] || []) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null; // null: a cycle exists
}

Похоже, но не то

Обход графа BFS / DFS: Топологическая сортировка упорядочивает DAG по зависимостям, а цикл означает, что корректного порядка вообще не существует. Обычный обход просто посещает все достижимые узлы и не даёт ни гарантии порядка, ни вердикта про цикл.

V, E до ~1e5, ориентированный граф зависимостей, нужен один корректный порядок или сообщение о цикле -> O(V+E): очередь по входящим степеням Кана посещает каждый узел и ребро один раз.

Изучить этот паттерн