关于dfs判环
  • 板块灌水区
  • 楼主一架飞机
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/19 20:00
  • 上次更新2023/10/27 06:52:23
查看原帖
关于dfs判环
151712
一架飞机楼主2022/10/19 20:00

这样为什么不行?

有向图,dfs遍历,如果遍历到一个走过并且dfn序大于等于rt(当前开始遍历的节点)的就是环

void dfs(int x){
	if(fl)return;
	dfn[x]=++iddfn;//if(x==48||x==88)clog<<x<<':'<<dfn[x]<<endl;
	for(int i=He[x];i;i=Nx[i]){
		int y=To[i];
		if(w[i]<=val)continue;
		if(dfn[y]&&dfn[rt]>dfn[y])continue;
		if(dfn[y]){fl=1;return;}
		dfs(y);
	}
}

//main函数里的
for(int i=1;i<=n;i++){
	if(dfn[i])continue;
	rt=i;dfs(i);
	if(fl)break;
}
2022/10/19 20:00
加载中...