对于求tarjan求割点的疑问
  • 板块学术版
  • 楼主wxw_zl
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/14 11:52
  • 上次更新2024/1/14 14:28:12
查看原帖
对于求tarjan求割点的疑问
469487
wxw_zl楼主2024/1/14 11:52
void tarjan(int x,int fa) {
	dfn[x]=low[x]=++cnt;
	vis[x]=1;
	int son=0;
	for(int i=head[x]; ~i; i=ne[i]) {
		int v=to[i];
		if(vis[v]) {
			if(v!=fa) {
				low[x]=min(low[x],dfn[v]);
          	//疑问处
			}
			continue;
		}
		tarjan(v,x);
		son++;
		if(low[v]>=dfn[x]&&x!=1)key[x]=1;
		low[x]=min(low[x],low[v]);
	}
	if(x==1&&son>=2)key[x]=1;
}

疑问:既然这里是在处理后向边,那low[x]不应该变成low[x]=min(low[x],low[v]);low[x]=min(low[x],low[v]);吗?子节点能够到达的最小编号不就是父亲能到达的最小编号吗?

改成low[x]=min(low[x],low[v]);low[x]=min(low[x],low[v]);为什么会错?

求教,悬赏关注。

2024/1/14 11:52
加载中...