1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void kahn() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (auto v : g[u]) {
            deg[v]--;
            if (!deg[v]) q.push(v);
        }
    }

    if (order.size() != n)
        cout << "cycle";
    else
        for (int i = 0; i < order.size(); i++) cout << order[i] << " ";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void dfs(int u) {
    color[u] = 1;
    for (auto v : g[u]) {
        if (color[v] == 1)
            cout << "cycle";
        else if (color[v] == 0)
            dfs(v);
    }
    color[u] = 2;
    order.push_back(u);
}

void topo_dfs() {
    for (int i = 1; i <= n; i++)
        if (color[i] == 0) dfs(i);
    reverse(order.begin(), order.end());
    for (auto u : order) cout << u << " ";
}