关于 tarjan 求强联通分量
  • 板块灌水区
  • 楼主StarsIntoSea
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/18 10:46
  • 上次更新2024/5/18 10:49:21
查看原帖
关于 tarjan 求强联通分量
1121518
StarsIntoSea楼主2024/5/18 10:46
void Tarjan(int x){
	tot++;
	dfn[x]=low[x]=tot;
	used[x]=1;
	stk[++top]=x; instack[x]=1;
	for(int i=0;i<(int)a[x].size();++i){
		int t=a[x][i];
		if(dfn[t]==0){
			Tarjan(t);
			low[x]=min(low[x],low[t]);
		}
		else if(instack[t]==1){
			low[x]=min(low[x],dfn[t]);
		}
	}
	if(dfn[x]==low[x]){   //<---------
		int t=0; ++cnt;
		while(t!=x){
			t=stk[top--];
			instack[t]=0;
			scc[t]=cnt;
			++siz[cnt];
		}
	}
}

在执行记录scc中,栈是不是每次都会清空?

2024/5/18 10:46
加载中...