史上代码最简单，讲解最清晰的双连通分量

约定不等于承诺〃 2021-11-23 23:22 422阅读 0赞

史上代码最简单，讲解最清晰的双连通分量

（需提前学习强连通分量）

双连通分量的主要内容包括割点、桥（割边）、点双和边双，分别对应 4 个 Tarjan 算法。

所有算法的时间复杂度均为 O(n + m)。

双连通分量用到 DFS 树的性质，所有的边分别树边和返祖边两类，大大简化了代码。

双连通分量具有大量的性质，要能熟练掌握。

一些定义：树枝边：DFS时经过的边(由上至下)；  
                 返祖边：与DFS方向相反，从某个节点指向某个祖先的边；

求割点：

割点性质：

（1）根结点如果是割点当且仅当其子节点数大于等于 2；  
    （2）非根节点 u 如果是割点，当且仅当存在 u 的一个子树，子树中没有连向 u 的祖先的边(返祖边)。

代码：

void tarjan(int u,int fa) //当fa=0时，说明该节点是根节点;
    {
        int num=0; //用来计量子节点数；
        low[u]=dfn[u]=++cur;
        for(int i=head[u];i;i=star[i].to){ //链式前向星存图;
            int v=star[i].to;
            if(!dfn[v]){
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
                if(!fa && ++num>1||fa && dfn[u]<=low[v]){  
                //1.根节点是割点，且子节点数大于等于2； 
                //2.非根节点是割点，且子节点中没有返祖边； 
                    cutpoint[u]=1; //标记该点为一个割点；
                }
            }
            else if(v!=fa){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }

求点双连通分量：

以下 3 条等价（均可作为点双连通图的定义）：  
　　（1）该连通图的任意两条边存在一个包含这两条边的简单环；  
　　（2）该连通图没有割点；  
　　（3）对于至少3个点的图，若任意两点有至少两条点不重复路径。

下面两句话看不看的懂都行：

点双连通分量构成对所有边集的一个划分。

两个点双连通分量最多只有一个公共点，且必为割点。进一步地，所有点双与割点可抽象为一棵树结构。

#include <bits/stdc++.h>
    using namespace std;
    struct littlestar{
        int to;
        int nxt;
    }star[200010];
    int head[200010],cnt;
    void add(int u,int v){
        star[++cnt].to=v;
        star[cnt].nxt=head[u];
        head[u]=cnt;
    } 
    int low[20010],dfn[20010],cur;
    pair<int,int> st[200010];
    int Top,num;
    vector<int> res[20010];
    void tarjan(int u,int fa)
    {
        low[u]=dfn[u]=++cur; 
        for(int i=head[u];i;i=star[i].nxt){ //链式前向星存图 
            int v=star[i].to;
            int top=Top;
            if(v!=fa && dfn[u]>dfn[v]){
                 st[++Top]=make_pair(u,v); //当这条边并不是通往父亲的边时，并且该点的子             
                                           //树中没有返祖边时，将这条边压入栈; 
            }
            if(!dfn[v]){
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
                if(dfn[u]<=low[v]){
                    ++num; //num表示第几个点双区域(一个图可能存在多个点双) 
                    for(;Top>top;Top--){ //类似于强连通分量的退栈过程； 
                        int x=st[Top].first;
                        int y=st[Top].second;
                        if(res[x].empty() || res[x].back()!=num){
                            res[x].push_back(num); //由于num递增,所以res[]递增,所以res[x]的最后
                                                   //如果不是num,就代表之前不会标记过该点; 
                        }
                        if(res[y].empty() || res[y].back()!=num){
                            res[y].push_back(num); //与上面的同理； 
                        }
                    }
                }
            }
            else if(v!=fa){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }

求桥：

桥的性质： (u; v)边在dfs 树中。不妨设u 为v 的父亲，v 的子树没有向u 或其祖先连的边。

void tarjan(int u,int fa)
    {
        bool flag=0; //用来判断是否存在重边
        low[u]=dfn[u]=++cur;
        for(int i=head[u];i;i=star[i].nxt){
            int v=star[i].to;
            if(!dfn[v]){
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
                if(dfn[v]==low[v]) //它的子节点v的子树中，没有像u或其祖先连的边(返祖边)
                {
                    bridge.push_back(i);  //桥的一个集合
                }
            }
            else if(v!=fa || flag){
                low[u]=min(low[u],dfn[v]);            
            }
            else flag=1;
        }
    }

求边双连通分量

以下3 条等价（均可作为边双连通图的定义）：

（1）该连通图的任意一条边存在一个包含这条边的简单环；  
    （2）该连通图没有桥；  
    （3）该连通图任意两点有至少两条边不重复路径。

下面两句话看不看的懂都行：

(1)边双连通分量构成对所有点集的一个划分。  
    (2)两个边双连通分量最多只有一条边，且必为桥。进一步地，所有边双与桥可抽象为一棵树结构。

#include <bits/stdc++.h>
    using namespace std;
    struct littlestar{
        int to;
        int nxt;
    }star[10010];
    int head[10010],cnt;
    void add(int u,int v){
        star[++cnt].to=v;
        star[cnt].nxt=head[u];
        head[u]=cnt;
    } 
    int st[5010],Top,num;
    int low[5010],dfn[5010],cur;
    int res[5010];
    int kk[150][150];
    int anss[5001];
    void tarjan(int u,int fa)
    {
        bool flag=0;
        low[u]=dfn[u]=++cur;
        st[++Top]=u;
        for(int i=head[u];i;i=star[i].nxt){
            int v=star[i].to;
            if(!dfn[v]){
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
            }
            else if(v!=fa || flag){
                low[u]=min(low[u],dfn[v]);
            }
            else flag=1;
        }  //到此为止与求桥的意义差不多
        if(low[u]==dfn[u]){ //u的子树中，没有返祖边
            num++;
            int tmp;
            do{
                tmp=st[Top--]; //退栈,原来栈中的元素构成一个边双
                res[tmp]=num;
            }while(tmp!=u);
        }
    }

转载于:https://www.cnblogs.com/kamimxr/p/11053539.html