P1137 旅行计划

#include <bits/stdc++.h>
using namespace std;
#define top front
const int N=2e5+5;
int n,m,x,y,tp[N],t;
int in[N],out[N],dp[N];
vector<int> g[N];
queue<int> q;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        cin>>x>>y;
        g[x].push_back(y);
        ++in[y],++out[x];
    }
    for(int i=1;i<=n;++i)
        if(!in[i])  q.push(i),tp[++t]=i;
    // TopoSort
    while(!q.empty()) {
        int v=q.top();q.pop();
        for(auto i:g[v]) {
            if(--in[i]==0)
                q.push(i),tp[++t]=i;
        }
    }
    // DP
    for(int i=1;i<=n;++i)   dp[i]=1;
    for(int i=1;i<=n;++i) {
        int u=tp[i];
        for(auto j:g[u])
            dp[j]=max(dp[j],dp[u]+1);
    }
    for(int i=1;i<=n;++i)   cout<<dp[i]<<endl;
    return 0;
}