[图论]无向图双连通分量

· · 个人记录

无向图双连通分量

各种定义

无向图的割点

给定无向图 G =（V，E ）;

若对x \in V ，从图中删去节点 x 以及所有与 x 关联的边之后，G 分裂成两个或 两个以上不相连的子图，则称 x 为G的割点；

​ ——《算法竞赛进阶指南》

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点.集合

如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点。

​ ——《百度百科》

eg:

给定一个无向图，此时他的连通分量为1（就是他自己）

那么，图中删去的这个点就是这个无向图的一个割点，此时无向图的连通分量个数 为3

无向图的割边（桥）

给定无向图 G =（V，E ）;

若对e \ in E ，从图中删去边 e 之后，G 分裂成两个或两个以上不相连的子图， 则称 e 为G的桥或割边；

​ ——《算法竞赛进阶指南》

假设有连通图 G ，e 是其中一条边，如果 G - e 是不连通的，则边 e 是图 G的一条割边。此情形下，G - e 必包含两个连通分支；

​ ——《百度百科》

eg:

还是一个无向图

点双连通图

若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。

​ ——《百度百科》

边双连通图

若一个无向图中的去掉任意一条边都不会改变此图的连通性，即不存在割边（桥），则称作边双连通图。

​ ——《百度百科》

双连通分量

无向图的极大点双连通子图被称为“点双连通分量”，简记为“v-DCC”，即“vertex double connected component”的缩写。无向图的极大边双连通子图被称为“边双连通分量”，简记为“e-DCC”，即“edge double connected component”的缩写。二者统称“双连通分量”,简记为“DCC”。

​ ——《百度百科》

注意

1.一般在不连通图上讨论双连通没有意义

2.在边双连通分量中，点恰属于一个边双连通分量；

3.在点双连通分量中，边恰属于一个点双连通分量；

Tarjan 算法

这里只是无向图的Tarjan算法；

目的

求出无向图的所有割点，割边，以及点双连通分量和边双连通分量；

时间复杂度

O（m + n）

实现

搜索树

在无向图中任选一个节点出发进行深度优先遍历，每个点只访问一次，所有发生递归的边（x，y）(换言之，从x到y是对y的第一次访问)构成一棵树，我们把这棵树称为“无向连通图的搜索树”。当然，一般无向图（不一定连通）的各个连通块的搜索树构成无向图的“搜索森林”；

前置

对于每一个点u

引入一个时间戳 dfn[u] ,即在深度优先遍历中，按照每个节点第一次被访问的时间顺序，依次给予N个点1 ~ N的整数标记；

引入一个追溯值（这个名字奇奇怪怪）low[u],

设subtree(u)表示搜索树中以u为根的子树，low[u]定义为以下节点时间戳的最小值：

1.subtree(u)上的点；

2.通过一条不在搜索树上的边，能够到达subtree(u)的节点；

​ ——《算法竞赛进阶指南》

其实low[u]表示从u出发不走通向u父亲的边（即不是从u返回上一个点）能到达的dfn的最小值；

要注意看有没有重边和自环！！ (会影响到细节的处理)；

求割边

割边判定法则

无向边（x , y）是桥，当且仅当搜索树上存在 x 的一个子节点y满足：dfn[x]<low[y]；

证明：根据定义，dfn[x]<low[y]说明从subtree（y）出发，不经过（x,y）的前提下，不管走哪一条边，都无法访问到x或比x更早访问到的点。如果把（x,y）删除，那么subtree（y）就与x断开，没有与x相连的边，此时无向图断裂成了两部分，因此（x,y）是割边，反之，如果不存在这样的子节点y,使得dfn[x]<low[y]，则说明每一个subtree(z)(z是x的子节点)，都能绕行其他边到达x或比x更早访问到的点（即（x，z）在环上），(x,z)自然不是割边；

求割边的Tarjan代码
void tarjan(int now,int fa)//now为现在访问到的节点的编号
{                        //fa为now的父亲节点的编号；
    dfn[now]=++tot;//时间戳
    low[now]=tot;
    for(int j=hd[now];j!=-1;j=edge[j].nxt)//链式前向星存图
    {
        if(edge[j].to!=fa && dfn[edge[j].to])//如果下一个点不是父亲，继续往下搜
        {
            low[now] = min(low[now], dfn[edge[j].to]);//维护low数组
        }
        if(!dfn[edge[j].to])
        {
            tarjan(edge[j].to,now);
            low[now]=min(low[now],low[edge[j].to]);//维护low数组
            if(low[edge[j].to]>dfn[now])//判是不是割边
            {
                printf("%d %d\n",now,edge[j].to);
            }
        }
    }
    //如果是有重边的无向图，则now和fa都应该记录边的编号
    //即now表示现在搜索到的边的编号，fa表示上一条搜索到的边的编号
}
signed main()
{

    //...                 //读入+存图

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])//如果还没有访问过，说明这个点和之前所有点都不连通
        {
            tarjan(i,0);//从他开始访问
        }
    }
}

求割点

割点判定法则

1.如果点x不是搜索树的根节点，则x为割点当且仅当搜索树上存在一个x的子节点y满足dfn[x]<=low[y]。

2.特别的，如果x是根节点，则要求至少有两个x的子节点y_1 y_2满足上述条件

证明：

1.证明类似于割边判定法则的证明，即若果满足dfn[x]<=low[y],说明节点y无法走到比x更显访问到的节点，删去x之后，subtree(y)会构成一个单独的连通块，而由于x点并不是根节点，因此连通分量数必定会增加，x是割点

2.显然成立，因为x是搜索树上的根节点，他的时间戳dfn[x]与如low[x]都为1，其所有子节点的low[y]必然大于等于dfn[x]。如果有两个及两个以上的节点就说明删去x以后，这两个子节点不能互相到达，所以连通分量数增加，x为割点

求割点的Tarjan代码
void tarjan(int now)
{
    dfn[now]=++tot;//时间戳
    low[now]=tot;
    bool fl=0;//打标记
    int son=0;//符合标准的儿子数
    for(int j=hd[now];j!=-1;j=edge[j].nxt)//链式前向星
    {
        int v=edge[j].to;
        if(dfn[v])//在走（now,v）这条边以前就已经访问过，v不是now的儿子
        {
            low[now]=min(low[now],dfn[v]);//维护low数组
        }
        else//没有访问过，即从（now,v）是对于v的第一次访问
        {
            tarjan(v);//往下搜索
            son++;//now的儿子数++;
            low[now]=min(low[now],low[v]);//维护low数组
            if(dfn[now]<=low[v] && now!=root)//关于是否为割点的判定1
            {                           //即对于非根节点的判定
                fl=1;
            }
        }
    }
    if(fl || (now==root && son>1))//关于是否为割点的判定2
     {                          //即对根节点的判定      
        printf("%d ",now);
    }
}
signed main()
{

    //...                 //读入+存图

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])//如果还没有访问过，说明这个点和之前所有点都不连通
        {
            root=i;
            tarjan(i);//从他开始遍历
        }
    }
}
注意

再求割点或者点双连通分量时，不能把非树边的更新方式 low[u]=min(low[u],dfn[v])写成low[u]=min(low[u],low[v]);

求边双连通分量

小技巧

易征得，一个点最多属于一个边双连通分量（因为如果一个点属于多个边双连通分量，这些边双连通分量是可以合并的）

所以某些时候，我们处理割边时，可以认为其是大小为2的双连通分量

这样在有时候可以节约代码复杂度

一个点最多属于任意个点双连通分量（菊花图的中间的那个节点） 但是特殊情况往往需要单独讨论 因此，我们把它画成带环的

方法1

直接利用刚才的方法求出所有割边，删去这些边，得到的新图 G' 中的每一个连通分量都是边双连通分量

代码实现
void tarjan(int now,int fa)//now和fa都是点的编号
{
    dfn[now]=++tot;//时间戳
    low[now]=tot;
    for(int j=hd[now];j!=-1;j=edge[j].nxt)//链式前向星
    {
        int v=edge[j].to;
        if(!dfn[v])//如果没有访问过v,即（now,v）是对于v的第一次访问
        {
            tarjan(v,now);//从v继续搜
            low[now]=min(kow[now],low[v]);//维护low数组
            if(low[v]>dfn[now])//判断为割边
            {
                printf("%d %d\n",now,v);
                is_bridge[j]=1;//记录这一条边是桥
                //记录这条边的反向边是桥（毕竟是无向图）
                if(j&1)//如果j是奇数，那么j的反向边为j+1
                {
                    is_bridge[j+1]=1;
                }
                else//如果j是偶数,那么j的反向边为j-1
                {
                    is_bridge[j-1]=1;
                }
            }
        }
        else if(v!=fa)//如果v不是第一次访问，且不是搜索树上now的父亲
        {
            low[now]=min(low[now],dfn[v]);//维护low数组
        }
    }
}
signed main()
{

    //...                 //读入+存图

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])//如果还没有访问过，说明这个点和之前所有点都不连通
        {
            tarjan(i,0);//从他开始遍历
        }
    }
}
方法2

在求割边时维护一个栈，每遍历到一个节点u,就将u压栈，如果在遍历完与u相连的所有边后（即更新完low[u]之后），如果low[u]=dfn[u]，说明u是u所在边连通分量中最先被访问的节点，不断弹栈知道弹出u，这个过程中弹出的节点就是u所在边连通分量中的节点

代码实现
stack <int> q;
void tarjan(int now,int fa)
{
    dfn[now]=++tot;//时间戳
    low[now]=tot;
    q.push(now);//维护栈，即维护访问次序
    vis[now]=1;//打标记
    for(int j=hd[now];j!=-1;j=edge[j].nxt)//链式前向星
    {
        int v=edge[j].to;
        if(!dfn[v])//如果没有访问过v,即（now,v）是对于v的第一次访问
        {
            tarjan(v,now);//从v继续搜
            low[now]=min(kow[now],low[v]);//维护low数组
        }
        else //如果v不是第一次访问
        {
            low[now]=min(low[now],dfn[v]);//维护low数组
        }
    }
    if(dfn[now]==low[now])//满足判定条件
    {
        bcc++;//新的边双连通子图
        while(1)//不断弹栈
        {
            int tmp=q.top();
            q.pop();
            vis[tmp]=0;//清空标记
            belong[tmp]=bcc;//记录这个点属于哪一个边双连通子图
            if(tmp==now) //弹栈弹到了now，跳出循环
            {
                break;
            }
        }
    }
}
signed main()
{

    //...                 //读入+存图

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])//如果还没有访问过，说明这个点和之前所有点都不连通
        {
            tarjan(i,0);//从他开始遍历
        }
    }
}

求点双连通分量

小知识

一张连通图，点数大于1,不存在大小为1的点双连通分量，大小至少为2（点数），边数最小为1

证明：

这是一个大小为2的点双连通分量

那么对于任意一个点，都可以加上一条边，使它变成大小至少为2的点连通子图，那么大小为1的点双连通子图就必然不可能为极大的点双连通子图，即不可能为点双连通分量

当然，如果这个连通图只有一个点，这也就是一个大小为1 的点双连通分量（毕竟就它一个）

方法

类似于求边双连通分量时的方法2类似，每遍历到一个节点u，就把u压栈。如果(u,v)是搜索树上的一条边，（约定u是v的父亲），满足dfn[u]<=low[v],即u是一个割点，这时不断弹栈，知道栈顶为u，要记录u，但不弹出u，这个过程中弹出的点就构成了这张无向图的一个点双连通分量。

代码实现
stack <int> q;
vector <int> v-DCC[...];
void tarjan(int u)
{
    dfn[u]=++tot;//时间戳
    low[u]=tot;
    q.push(u);//维护栈，即维护访问次序
    for(int j=hd[u];j!=-1;j=edge[j].nxt)//链式前向星
    {
        int v=edge[j].to;
        if(!dfn[v])//如果没有访问过v,即（u,v）是对于v的第一次访问
        {
            tarjan(v);//从v继续搜
            low[u]=min(low[u],low[v]);//维护low数组
            if(dfn[u]<=low[v])//如果满足条件，即u是一个割点
            {
                bcc++;//一个新的点双连通子图
                while(q.top()!=u)//不断弹栈直到栈顶为u
                {
                    int tmp=q.top();
                    q,pop();
                    v_DCC[bcc].push_back(tmp);
                    //把弹出的点加入到点双连通子图中
                }
                v_DCC.push_back(u);//把u加入到点双连通子图中
            }
        }
        else
        {
            low[u]=min(low[u],dfn[v]);//维护low数组
        }
    }
}
signed main()
{

    //...                 //读入+存图

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])//如果还没有访问过，说明这个点和之前所有点都不连通
        {
            tarjan(i);//从他开始遍历
        }
    }
}

后话

这里只是对于无向图双连通分量的知识整理，并没有例题。

关于无向图双连通分量，有几个定义绕来绕去，而且Tarjan代码大同小异，因此需要格外注重细节

eg:

1.割边 dfn[x]<low[y];

割点 dfn[x]<=low[y];

2.if(!dfn[v]) low[u]=min(low[u],low[v]);

else low[u]=min(low[u],dfn[v]);

3.求双连通分量时，边双连通分量要弹出u,而点双连通分量中不弹u

.......

因此，细节决定成败。

谢谢观看。