tarjan 这样写是对的吗
查看原帖
tarjan 这样写是对的吗
761125
Milthm楼主2024/10/22 16:25
void tarjan(int u){
	st[++top]=u;vis[u]=1;dfn[u]=low[u]=++idx;
	for(int v:e[u]){
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(vis[v])low[u]=min(low[u],low[v]);
        //就是这两个更新,我写的都是 low[u]=min(low[u],low[v])
	}
	if(low[u]==dfn[u]){
		++cnt;
		do{
			vis[st[top]]=0;id[st[top]]=cnt;s[cnt]+=a[st[top]];
		}while(st[top--]!=u);
	}
}
2024/10/22 16:25
加载中...