关于存在性的问题
查看原帖
关于存在性的问题
389133
514InParadox楼主2022/1/22 10:00

众所周知,tarjantarjan 求割点时有这么一句话

if(dfn[u]<=low[v]&&u!=root)cut[u]=true;

其意为在搜索树上,对于作为 uu 儿子的 vv,如果 vv 不能到达 uu 的祖先,那么代表 vv 只能通过 uu 到达 uu 的祖先,即 uu 是割点。

但是如果 vv 不是 uu 的儿子,显然有 lowvdfnv<dfnulow_v \leq dfn_v < dfn_u

也就是说如果 vv 不是 uu 的儿子,则判断句 dfnulowvdfn_u\leq low_v 必定不成立。所以不管 vv 是不是 uu 的儿子,我们都可以进行上述判断并且对答案没有影响。

那么我们的 tarjantarjan 割点代码可以写成这样:

int child=0;
dfn[u]=low[u]=++deep;
for(int i=head[u];i;i=edge[i].next)
{
	int v=edge[i].to;
	if(!dfn[v])
	{
		child++;
		tarjan(v,root);
		low[u]=min(low[u],low[v]);
	}
	if(dfn[u]<=low[v]&&u!=root)cut[u]=true;
	low[u]=min(low[u],dfn[v]);
}
if(u==root&&child>=2)cut[u]=true;

然而这种写法是一个点也过不了的,并且其与AC代码的唯一差别就是最开始提到的语句是否在第二个大括号内。

不理解哪里出了问题,请巨巨们帮忙看一下orz

2022/1/22 10:00
加载中...