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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
  • Порядок топологической сортировки — порядок убывания времени выхода из вершины.
  • Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
vector<vector<int>> g(n);
vector<bool> visited(n);
vector<int> order;

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

for (int v = 0; v < n; v++)
    if (!visited[v])
        dfs(v);
reverse(order.begin(), order.end());

Ссылки на задачи

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Топологическая_сортировка&oldid=2500