关于广义圆方树访问子节点访问父节点continue的问题
查看原帖
关于广义圆方树访问子节点访问父节点continue的问题
225515
Forg1weN楼主2023/8/26 07:30
void tarjan(int x,int F) {
	dfn[x]=low[x]=++num;
	Q[++tp]=x;
	for(int i=E.hd[x];i;i=E.edge[i].nt) {
		int y=E.edge[i].v;
		int w=E.edge[i].w;
		if(y==F)continue;//here
		if(!dfn[y]) {
			val[y]=w;
			dis[y]=dis[x]+w;
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]) {
				++tot;
				r[tot]=val[Q[tp]]+dis[Q[tp]]-dis[x];
				T.addedge(tot,x,0);
				T.addedge(x,tot,0);
				v_dcc[tot].push_back(x);
				int z=0,len=0;
				do {
					z=Q[tp--];
					int len=dis[z]-dis[x];
					len=min(len,r[tot]-len);
					T.addedge(tot,z,len);
					T.addedge(z,tot,len);
					v_dcc[tot].push_back(z);
				}while(z!=y);
			}
		}
		else if(dfn[y]<dfn[x])
			val[x]=w,low[x]=min(low[x],dfn[y]);
	}
}

为什么要有注释这一步,平常求点双联通分量没有这句话都能过,有的人说是为了找环而非点双,但是点双不就是环吗?求大佬专业解释

2023/8/26 07:30
加载中...