拓扑排序算法

// https://www.luogu.com.cn/blog/arookieoier/p1137-lv-xing-ji-hua-ti-xie
//落谷1137旅行计划
#include
#include
#include
#include

using namespace std;
int n,m;
const int N=100005;
int h[N],next[4*N],to[4*N],w[4*N],idx=0,ind[4*N];

int hh=1,tt=0,cnt=0,q[4*N];
int dis[N];

void add(int u,int v,int val)
{
	to[++idx]=v;
	w[idx]=val;
	next[idx]=h[u];
	h[u]=idx;
}

void top_sort()
{
	for(int i=1;i<=n;i++)
	{
		if(ind[i]==0){
			q[++tt]=i;
		}
	}
	while(hh<=tt)
	{
		int u=q[hh++];
		for(int i=h[u];i;i=next[i])
		{
			int v=to[i];
			ind[v]--;
		//	dis[v]=dis[u]+1;
		//  if dis[v]
            dis[v]=max(dis[v],dis[u]+1);//是以v为原点接收的 每一个都是可以达到的无向图，所以要在外面算dsi 
			if(ind[v]==0){
				q[++tt]=v;
			//	dis[v]=dis[u]+1;
			}
		}
	}
}

int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v,0);
		ind[v]++;
	}
	top_sort();
	for(int i=1;i<=n;i++)//按照顺序来输出，并且把自身城市1加上去
	{
		cout<<dis[i]+1<<endl;
	}
	return 0;
}