tarjan 系列之 “割点”

· · 题解

  1. 强连通分量、割点、割边、点双连通分量、边双连通分量的区分。

可能这个很多人搞不清楚。割点、割边（又称桥）、点双连通分量（简称点双）、边双连通分量（简称边双）四个都是无向图中的概念；强连通分量和 “缩点” 操作是有向图中的概念。

割点和点双通常一起出现，割边和边双通常一起出现。

“分量” 一般是定义子图的，比如点双连通分量是无向图的极大双连通子图。“xxx 分量” 和 “xxx 图” 在性质上一般没有区别。

  1. tarjan 系列怎么学？先学什么？

先学割点是没问题的，因为这些你学会一个其它的也都会了。从难度角度，本人也认为割点在 tarjan 家族难度不高，至少比强连通分量好理解。

  1. 割点、点双的定义？

一个无向图如果去掉某个节点和它的所有边就不再连通，那么这个点叫做割点；

如果一个无向图去掉任意一个节点都连通，即不存在割点，那么这个图叫做点双连通图；

一个无向图中的每个极大点双连通子图称作此无向图的点双连通分量。

说白了，割点就是删掉后使图从连通变成不连通的点，在点双中不存在割点。

割边和边双的定义其实可以类比。

  1. 点双和边双的关系有什么特殊性？

首先，很显然，点双、边双一定是一个连通块。一个连通块不一定是点双、边双。

其次，除两点一线的特殊情况，点双一定是边双，反之不一定。

  1. 怎么求割点？

正片开始。P3388 【模板】割点（割顶）

以下说的是连通图，不连通分别做就行。

我们要接触到 tarjan 家族的老朋友：

这样，我们可以对边集 E 进行分类：\forall e \in E' 叫做树边，\forall e \in \complement_E E' 叫做非树边。

因为 dfs 到了一个节点会走完能走的边，我们能注意到，每条非树边两边的节点在 dfs 树中一定连接了祖先和子孙，我们把这种边叫做返祖边。不存在没有祖先子孙关系的非树边。也就是说，假设一条边 e 连接了节点 v_1 v_2，则 lca_{v_1,v_2}=v_1 或 v_2。之所以这么强调，是因为在有向图中，存在连接没有祖先子孙关系的非树边，叫做横叉边，这是一个不同点。

那么这两个数组怎么算？首先，第一次搜到 u 时，可知 dfn_u 可以直接知道，low_u 初始先赋为 dfn_u（不会更大）。

扫 u 的每条边，设这条边连接的另一个点是 v，如果 v 没有被搜过，这条边就是一条树边，那么就先处理 v，再将它的 low_v 更新给 low_u。 如果 v 被搜过了，这条边就是一条返祖边，那么用它的 dfn_v 更新 low_u。 用 dfn_v 更新而不是 low_v 更新的原因在于我们对 low 数组的定义是只允许经过一条非树边，如果用 low_v 更新，会出现错误（见下文）。

接下来看割点怎么判断。

对于非根节点 u，如果存在一个子结点 v 满足 low_v\ge dfn_u，说明 v 无法不经过点 u 到比 u 的 dfn 更小的节点。因此，如果删去 u，存在不连通的点。u 就是割点了。如果不存在这样的子节点，意味着 u 两边的节点一定存在不经过 u 相到达的方式，u 一定不是割点。

现在讲为什么返祖边的情况里 low_u 用 low_{fa} 更新会有细节的问题：若一个节点 u 自己有返祖边，第一次搜索到自己时，自己的 low 先被 low_{fa} 更新了；但是接下来访问到的某个子节点 v 又有到 u 的返祖边，low_u 又更新了 low_v，导致本来 u 节点是割点，从 v 节点跳不出去的情况，被当作可以，判断有误。

对于根节点，因为它的 dfn 一定最小，所以上述判断方法不适用。它的判断方法：如果有两个以上子节点，它就一定是割点，否则一定不是。

void tarjan(int x)
{
    int child=0;
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);

            if(x==root)child++;
            if(dfn[x]<=low[y]&&x!=root)
            IsCut[x]=1;
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(x==root&&child>=2)
        IsCut[x]=1;
}

int main()
{
    rd(n,m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        rd(u,v),add(u,v),add(v,u);
    }

    for(int i=1;i<=n;i++)
    if(!dfn[i]) root=i,tarjan(i);

    int ans=0;
    for(int i=1;i<=n;i++)
        if(IsCut[i]) ans++;
    wt(ans,'\n');
    for(int i=1;i<=n;i++)
        if(IsCut[i]) wt(i,' ');
    return 0;
}

有问题评论指出，随时解释 or 改正。