Help! I have a problem!
查看原帖
Help! I have a problem!
794148
cyx20091026楼主2025/1/21 14:04

为什么在tarjan深搜的过程中不用判断是否它走了来时路的反边?这样难道不会使else多执行吗?

void tarjan(int u,int fa){
	dfn[u]=low[u]=++num;
	int son=0;
	for(int i=head[u];i!=-1;i=edge[i].nxt){
		int v=edge[i].to;
		if(fa==v)  continue;//为何这段不需要?
		if(!dfn[v]){
			son++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=R){
				cnt+=!buc[u];
				buc[u]=1;
			}
		}
		else{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(son>=2&&u==R) cnt+=!buc[u],buc[u]=1;
}
2025/1/21 14:04
加载中...