蓝桥杯备考：图的遍历

这道题乍一看好像没什么不对的，但是！但是！结点最大可以到10的5次方！！！我们递归的时间复杂度是很高的，我们正常遍历是肯定通过不了的，不信的话我们试一下

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int n,m;
vector<int> edges[N];
bool st[N];
int ret;
void dfs(int u)
{
	for(auto&e : edges[u])
	{
		if(!st[e])
		{
			ret = max(ret,e);
			st[e] = true;
			dfs(e);
		}
	}
}
int main()
{
	cin >> n >> m;
	
	for(int i = 1;i<=m;i++)
	{
		int x,y;cin >> x >> y;
		edges[x].push_back(y);
	}
	for(int i =1;i<=n;i++)
	{
		memset(st,false,sizeof(st));
		st[i] = true;
		ret = i;
		dfs(i);
		cout << ret << " ";
	}
	
	
	
	return 0;
}

正着来，我们的时间复杂度很高

如果正着来，我们需要从1开始遍历图一遍，遍历到5再回去找6，从2再来一遍，遍历到1，回去找6，这时候我们的时间复杂度就是N平方，

我们不如把图反过来，反着找，把每次能到达最大点的编号标记上，然后下次再遍历的时候如果某个点已经被标记了就剪掉，时间复杂度就是O（N）

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5+10;
vector<int> edges[N];
int ret[N];
int n,m;
void dfs(int x,int n)
{
	ret[x] = n;
	for(auto &e : edges[x])
	{
		if(ret[e]) continue;
		ret[e] = n;
		dfs(e,n);
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i<=m;i++)
	{
		int x,y; cin >> x >> y;
		edges[y].push_back(x);
	}
	//上面表示存反图
	for(int i = n;i>=1;i--)
	{
		if(ret[i]) continue;
		dfs(i,i);
	 } 
	
	for(int i =1;i<=n;i++)
	{
		cout << ret[i] << " ";
	}
	
	return 0;
}