蒟蒻对了但有个有个老师都没解决的问题
查看原帖
蒟蒻对了但有个有个老师都没解决的问题
275989
LingHusama楼主2023/7/18 15:31

这是我tarjan 代码,过了的,但是想知道:

low[x]=min(low[x],dfn[to]);

(在倒数第10行)

为什么前面打和不打else都是对的,是数据问题吗?

void tarjan(int x,int fa){
	++t;
	dfn[x]=t;
	low[x]=t;
	top++;
	s[top]=x;
	bool f=0;//用来判重边,自环 
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i];
		
		if(to==fa&&f==0){
			f=1;
			continue;
		}
		if(!dfn[to]){
			tarjan(to,x);
			low[x]=min(low[x],low[to]);
		}
		low[x]=min(low[x],dfn[to]);
	}
	if(low[x]==dfn[x]){
		cnt++;
		while(s[top+1]!=x){
			bcc[cnt].push_back(s[top]);
			top--;	
		}
	}
}
2023/7/18 15:31
加载中...