洛谷 - P3916 图的遍历(dfs+反向建图)

洛谷 - P3916

思路

一开始用邻接表+bfs做，t得很惨，只能拿60分
原因是很多点其实被走过了，但是又不得不再走一次，因为前一次经过的时候，只得到了它某个前驱节点能走到的最大编号点，它能走到的最大点还是没得到

改了改思路，反向建图+dfs。从最大的点开始搜，经过一个点，便给这个点标记上最大点，因为遍历顺序是从最大的开始，所以被标记后就不会再次被更新，这样思路可以ac

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<set>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n,m;
int h[N],e[N],ne[N],idx;
int cnt[N];
bool st[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u, int mmax){
if(st[u])
return ;
cnt[u]=max(cnt[u],mmax);
st[u]=true;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j,mmax);
}
}
int main(void){
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(b,a);
}
for(int i=n;i>0;i--)
dfs(i,i);
for(int i=1;i<=n;i++)
printf("%d ",cnt[i]);
return 0;
}
/*
* When ability does not derserve ambition, just keep moving
*/

最后

以上就是柔弱电脑为你收集整理的洛谷 - P3916 图的遍历(dfs+反向建图)的全部内容，希望文章能够帮你解决洛谷 - P3916 图的遍历(dfs+反向建图)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。