关于tarjan
  • 板块学术版
  • 楼主ExBritainia
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/10/17 20:34
  • 上次更新2023/11/4 03:27:15
查看原帖
关于tarjan
95453
ExBritainia楼主2021/10/17 20:34
void tarjan(int x){
	dfn[x]=low[x]=++id;s[++t]=x;
	for(int i=0,y;i<g[x].size();i++)
		if(!dfn[y=g[x][i]]){
			tarjan(y);low[x]=min(low[x],low[y]);
			if(dfn[x]>low[y]) continue;
			c2++;add(x,c2);add(c2,x);int z=0;
			while(z!=y){z=s[t--];add(c2,z);add(z,c2);}//区别在这
		}else low[x]=min(low[x],dfn[y]);
}
void tarjan(int x){
	dfn[x]=low[x]=++id;s[++t]=x;
	for(int i=0,y;i<g[x].size();i++)
		if(!dfn[y=g[x][i]]){
			tarjan(y);low[x]=min(low[x],low[y]);
			if(dfn[x]>low[y]) continue;
			c2++;add(x,c2);add(c2,x);int z=0;
			while(s[t]!=x){int z=s[t--];add(c2,z);add(z,c2);}
		}else low[x]=min(low[x],dfn[y]);
}

请问以上两种写法有什么区别?换成下面一种写法就会WA

2021/10/17 20:34
加载中...