众所周知,tarjan 求割点时有这么一句话
if(dfn[u]<=low[v]&&u!=root)cut[u]=true;
其意为在搜索树上,对于作为 u 儿子的 v,如果 v 不能到达 u 的祖先,那么代表 v 只能通过 u 到达 u 的祖先,即 u 是割点。
但是如果 v 不是 u 的儿子,显然有 lowv≤dfnv<dfnu。
也就是说如果 v 不是 u 的儿子,则判断句 dfnu≤lowv 必定不成立。所以不管 v 是不是 u 的儿子,我们都可以进行上述判断并且对答案没有影响。
那么我们的 tarjan 割点代码可以写成这样:
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