蓝桥杯备考：图的遍历

这道题乍一看好像没什么不对的，但是！但是！结点最大可以到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;
}