社区讨论

关于dfs判环

一一架飞机
灌水区参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo7s4wli
此快照首次捕获于
2023/10/27 06:52
2 年前
此快照最后确认于
2023/10/27 06:52
2 年前
查看原帖
这样为什么不行？
有向图，dfs遍历，如果遍历到一个走过并且dfn序大于等于rt（当前开始遍历的节点）的就是环
CPP
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;
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...