← all categories

Topo Sort 1db4c9c1

DFS topological sort with cycle detection on a directed graph, handles disconnected graphs. Returns {order, ok}; ok is false if the graph has a cycle (order is invalid in that case). Longest path in a DAG: relax edges once per node, in order.

Time: O(V + E). tested

content/graphs/topo-sort.h

pair<vector<int>, bool> topoSort(int n, vector<vector<int>> &adj) {
    vector<int> vis(n, 0), order;  // 0 = unvisited, 1 = on stack, 2 = done
    bool ok = true;
    auto dfs = [&](auto &&dfs, int u) -> void {
        vis[u] = 1;
        for (int v : adj[u]) {
            if (vis[v] == 1) ok = false;
            else if (!vis[v]) dfs(dfs, v);
        }
        vis[u] = 2;
        order.push_back(u);
    };
    for (int i = 0; i < n; i++) if (!vis[i]) dfs(dfs, i);
    reverse(order.begin(), order.end());
    return {order, ok};
}