【题解】
拓扑排序+DP即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 #define LL long long 6 #define rg register 7 #define N 200010 8 using namespace std; 9 int n,m,front,rear,q[N],f[N],in[N]; 10 bool vis[N]; 11 vector<int>to[N]; 12 inline int read(){ 13 int k=0,f=1; char c=getchar(); 14 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 15 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 16 return k*f; 17 } 18 inline void topu(int x){ 19 f[x]=max(f[x],1); vis[x]=1; q[front=rear=1]=x; 20 while(front<=rear){ 21 int u=q[front]; 22 for(rg int i=0,v;i<(int)to[u].size();i++){ 23 in[v=to[u][i]]--; f[v]=max(f[v],f[u]+1); 24 if(!in[v]){vis[v]=1; q[++rear]=v;} 25 } 26 front++; 27 } 28 } 29 int main(){ 30 n=read(); m=read(); 31 for(rg int i=1;i<=m;i++){ 32 int u=read(),v=read(); 33 to[u].push_back(v); in[v]++; 34 } 35 for(rg int i=1;i<=n;i++)if(!vis[i]&&!in[i]) topu(i); 36 for(rg int i=1;i<=n;i++) printf("%d ",f[i]); 37 return 0; 38 }