如果你WA80on最后两个点
查看原帖
如果你WA80on最后两个点
1073995
Saint_ying_xtf楼主2024/6/13 22:02

正确的应该是:

void tarjan(int x){
	dfn[x]=low[x]=++tot;
	vis[x]=vis2[x]=1;
	st.push(x);
	for(auto it:mp[x]){
		if(!dfn[it]){
			tarjan(it);low[x]=min(low[x],low[it]);
		}else if(vis[it]) low[x]=min(low[x],dfn[it]);
	}if(dfn[x]==low[x]){
		cnt++;
		while(st.top()!=x){
			num[cnt]++;col[st.top()]=cnt;vis[st.top()]=0;st.pop();
		}num[cnt]++;col[x]=cnt;vis[x]=0;st.pop();
	}
}

注意

不要把:

else if(vis[it]) low[x]=min(low[x],dfn[it]);

写成

else if(vis[x]) low[x]=min(low[x],dfn[it]);

2024/6/13 22:02
加载中...