原题链接

题解

一个节点的答案一定是最大父节点+1

code

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

int ans[100005]={0};
int in[100005]={0};
vector<int> G[100005];
struct unit
{
    int pos,order;
};
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        in[y]++;
    }

    queue<unit> q;
    for(int i=1;i<=n;i++)if(!in[i])q.push({i,1});//有向图，多个群/起点构成

    while(q.size())
    {
        int now=q.front().pos,order=q.front().order;
        ans[now]=order;
        q.pop();

        for(auto next:G[now])
            if(--in[next]==0) q.push({next,order+1});//为什么是由最晚消失的父节点传递，因为最晚消失也意味着旅行经过的城市也多,，进入队列时间也晚
    }

    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}