谁规定这题只能用DFS（多种AC）

这题其实只要有反向建图的思路，怎么遍历都可以

顺便记录一下一个问题，数据范围开大了会在大数据点TLE（神奇不？）

(鬼知道我为什么是先想到SPFA才想起来和BFS是等价的)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e5+10;

int n,m;
int dist[N];
bool st[N],vis[N];
int h[N],e[N],ne[N],idx;
queue<int> q;

inline void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
	idx++;
	return;
}

inline void bfs(int x)
{
	if(vis[x])
		return;
	memset(st,0,sizeof(st));
	q.push(x);
	st[x]=1;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(vis[j])
				continue;
			if(!st[j])
			{
				st[j]=1;
				dist[j]=max(dist[j],dist[t]);
				vis[j]=1;
				q.push(j);
			}
		}
	}
	return;
}

int main()
{
	memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(b,a);
	}
	for(int i=1;i<=n;i++)
		dist[i]=i;
	for(int i=n;i>=1;i--)
		if(!vis[i])
			bfs(i);
	for(int i=1;i<=n;i++)
		printf("%d ",dist[i]);
	return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],idx;
int dis[N];
bool st[N];

void add(int a,int b)
{
	ne[idx]=h[a];
	e[idx]=b;
	h[a]=idx;
	idx++;
	return;
}

void spfa(int x)
{
	memset(st,0,sizeof(st));
	queue<int> q;
	q.push(x);
	st[x]=1;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dis[t]>dis[j])
			{
				dis[j]=dis[t];
				if(!st[j])
				{
					st[j]=1;
					q.push(j);
				}
			}
		}
	}
}

int main()
{
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(b,a);
	}
	for(int i=1;i<=n;i++)
		dis[i]=i;
	for(int i=1;i<=n;i++)
	{
		spfa(i);
//		for(int j=1;j<=n;j++)
//			cout<<dis[j]<<' ';
//		cout<<endl;
	}
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<' ';
	return 0;
}