LP1137

崔冷亦

[C++] 纯文本查看 复制代码

#include<iostream>
#include<queue>
using namespace std;
int f[200001],in[200001],h[200001],tot,n,m;
queue<int> q;
struct Edge{
	int next,to;
}e[200001];
void add(int f,int t)
{
	e[++tot].to=t;
	e[tot].next=h[f];
	h[f]=tot;
}
void topsort()
{
	for(int i=1;i<=n;i++)
	{
		if(!in[i]) q.push(i);
		f[i]=1;
	}
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		for(int i=h[v];i;i=e[i].next)
		{
			int t=e[i].to;
			f[t]=max(f[t],f[v]+1);
			in[t]--;
			if(!in[t]) q.push(t); 
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		in[y]++;
	}
	topsort();
	for(int i=1;i<=n;i++) cout<<f[i]<<"\n";
	return 0; 
}