if位置对答案的影响

请问为什么在tarjan中，把判定割点的if写到if(!dfn[v]) 中是正确的，而写到外面是错的呢？

代码：

CPP

void tarjan(int u){
	dfn[u]=low[u]=++SEQ;
	int son=0;
	for(int i=f[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(!dfn[v]){
			son++;
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u^root) ans.insert(u);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(u==root&&son>1) ans.insert(u);
}

中的

CPP

if(low[v]>=dfn[u]&&u^root) ans.insert(u);

这句，写成

CPP

void tarjan(int u){
	dfn[u]=low[u]=++SEQ;
	int son=0;
	for(int i=f[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(!dfn[v]){
			son++;
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
		if(low[v]>=dfn[u]&&u^root) ans.insert(u);
	}
	if(u==root&&son>1) ans.insert(u);
}

就错了。

蒟蒻觉得，就算把这句放到if外面，点v没有进入 if(!dfn[v]) ，那么点v应该就是以前搜到过的。所以low[v]应当小于dfn[u]，也就记录不到ans里，不会对答案有影响...但是为什么放外面会0分，放里面就AC了

if位置对答案的影响

讨论操作

回复

相关推荐

if位置对答案的影响