思考
  • 板块学术版
  • 楼主formu1
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/8/30 15:16
  • 上次更新2023/11/3 00:20:53
查看原帖
思考
522930
formu1楼主2023/8/30 15:16

在强连通分量的代码中:

void tarjan(int u){
	low[u]=dfn[u]=++tim;
	stk[++stktop]=u;
	vis[u]=1;
	for(int i=headnext[u];i!=0;i=edge[i].next){
		int v=edge[i]._this;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		++cnt;
		int v;
		do{
			v=stk[stktop--];
			scc[v]=cnt;
			vis[v]=0;
		}while(u!=v);
	}
}

第十二行:low[u]=min(low[u],dfn[v]); 的 dfn[v] 能否换成 low[v]?

只需要保证他们的 dfn 一样是不是就可以了?

2023/8/30 15:16
加载中...