P3916 图的遍历题解

题目

给出N个点，M条边的有向图，对于每个点v，求A(v) 表示从点v出发，能到达的编号最大的点。

输入输出格式

输入格式

第1行2个整数N,M，表示点数和边数。

接下来M行，每行2个整数Ui​,Vi​，表示边 (Ui​,Vi​)。点用1,2,…,N编号。

输出格式

一行N个整数A(1),A(2),…,A(N)。

输入输出样例

输入样例

4 3
1 2
2 4
4 3

输出样例

4 4 3 4

解析

针对这个题目如果想对每个点做一次深度优先遍历或广度优先遍历，对于一次遍历的复杂度是，所以总复杂度是，不能接受。

所以一个简单的优化的想法是，在做深度优先遍历时，当需要求时，先设为自己的点标号u，然后求出它能直接到达的点v的，然后让当前的与取个最大值。这样求出所有的后，也得到了最后的，就避免了重复的计算。

但很可惜的是，这种方法有一个致命的漏洞。当使用深度优先遍历时，可能会搜索到之前正在被搜索而没有得到答案的点（也就是遇到环的情况）

为了解决这个出现环时答案没有更新好的问题，可以考虑换一个方法理解。之前是让点v去找它能到达的最大的点，现在让最大的点去告诉哪些点能到达它。用反向边建图，也就是，原图中如果有一条边<u,v>，那么不建<u,v>，而是建<v,u>。然后枚举点时从n枚举到1.然后从当前枚举的点u出发，让能用深度优先遍历或广度优先遍历到的且没有被更新过的点v的（因为在从n枚举到1时，被更新过的点一定是用比当前数字大的点更新的）。

#include<iostream>
#include<vector>
#define maxn 100005
using namespace std;
int n,m;
vector<int>p[maxn];
int a[maxn];
void solve(int x,int v){
	a[x]=v;//将点x的答案更新为v 
	for(int i=0;i<p[x].size();i++){
		if(!a[p[x][i]]){//如果答案没有被更新过，则用当前值的点更新 
			solve(p[x][i],v);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		p[v].push_back(u);
	}//反向建边 
	for(int i=n;i>=0;i--){
		if(a[i]==0){
			solve(i,i);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}