【題解】TIOJ 1929 . 偏序關係

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b, dfn[1000005], low[1000005], instk[1000005], idx, sccidx, scc[1000005];
vector <int> v[1000005], e[1000005];
stack <int> stk;

void dfs(int x){
    idx++;
    dfn[x] = idx;
    low[x] = idx;
    instk[x] = 1;
    stk.push(x);
    for (int i:v[x]){
        if (dfn[i]){
            if (!instk[i]) continue;
            low[x] = min(low[x], dfn[i]);
        }
        else{
            dfs(i);
            low[x] = min(low[x], low[i]);
        }
    }
    if (low[x] == dfn[x]){
        sccidx++;
        while (stk.top() != x){
            scc[stk.top()] = sccidx;
            instk[stk.top()] = 0;
            stk.pop();
        }
        scc[x] = sccidx;
        instk[x] = 0;
        stk.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i <= n; i++){
        if (!dfn[i]) dfs(i);
    }
    int in[sccidx+1] = {};
    for (int i = 1; i <= n; i++){
        for (int j:v[i]){
            if (scc[i] != scc[j]){
                e[scc[i]].push_back(scc[j]);
                in[scc[j]]++;
            }
        }
    }
    queue <int> q;
    int ansidx = 0, ans[sccidx+1] = {};
    for (int i = 1; i <= sccidx; i++){
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()){
        int x = q.front();
        q.pop();
        ansidx++;
        ans[x] = ansidx;
        for (int i:e[x]){
            in[i]--;
            if (in[i] == 0) q.push(i);
        }
    }
    cout << ansidx << "\n";
    for (int i = 1; i <= n; i++){
        cout << ans[scc[i]] << " ";
    }
    cout << "\n";
}