Tarjan算法求双连通分量

Tarjan算法求双连通分量

  • 双连通
    1. 边双连通:连通的无向图中,对于两个点 uv ,如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说 uv 边双连通
    2. 点双连通:连通的无向图中,对于两个点 uv ,如果无论删去哪个点(只能删去一个,且不能删uv 自己)都不能使它们不连通,我们就说uv 点双连通
    3. 边双连通具有传递性,即,若x,y 边双连通,y,z 边双连通,则x,z 边双连通。
    4. 点双连通 具有传递性,反例如下图,A,B 点双连通,B,C 点双连通,而A,B 点双连通。

Tarjan算法求双连通分量

  • 割点和割边

    1. 割点:对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。

      • 割点的性质:

        1. 根结点:如果是割点条件是,当且仅当其子节点数大于等于 2
        2. 非根节点u 如果是割点,当且仅当 u 至少存在一个子树vv中没有连向 u 的祖先的边(返祖边)。即v访问结束时满足low[v]>=dfn[u]
        • code

          void tarjan(int u,int fa){ //当fa=0时,说明该节点是根节点;
              int num=0; //用来记录子节点数;
              low[u]=dfn[u]=++Time;
              for(int i=head[u];i;i=e[i].next){
                  int v=e[i].to;
                  if(!dfn[v]){//v为白点,即(u,v)为树枝边
                      tarjan(v,u);
                      low[u]=min(low[u],low[v]);
                      if(!fa && ++num>1||fa && low[v]>=dfn[u]){  
                      //1.根节点是割点,且子节点数大于等于2; 
                      //2.非根节点是割点,且子节点中没有返祖边; 
                          cutpoint[u]=1; //标记该点为一个割点;
                      }
                  }
                  else if(v!=fa){//返祖边
                      low[u]=min(low[u],dfn[v]);
                  }
              }
          }
          
    2. 割边:对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。

      • 桥的性质:

        1. (u, v)dfs 树中。如果uv 的父亲,v 的子树中没有向u 或其祖先连的边。

        2. 如果桥(u,v)的两个端点都不是叶子节点,则节点uv为割点。

        • code

          void tarjan(int u,int fa){
              bool flag=0; //用来判断是否存在重边
              low[u]=dfn[u]=++Time;
              for(int i=head[u];~i;i=e[i].next){
                  int v=e[i].to;
                  if(!dfn[v]){
                      tarjan(v,u);
                      low[u]=min(low[u],low[v]);//儿子更新父亲
                      if(dfn[v]==low[v]){//它的子节点v的子树中,没有像u或其祖先连的边(返祖边)
                          bridge[i]=bridge[i^1]=1;  //边i和i的反向边是桥,边的编号从0开始
                      }
                  }
                  else if(v!=fa){
                      low[u]=min(low[u],dfn[v]);            
                  }                  
              }
          }
          
  • 双连通分图

    1. 边双连通图:如果任意两点至少存在不重复路径,则称该图为边双连通的。

      • 边双连通图的定义等价于任意一条至少在一个简单环中。

      • 边连通分量:边双连通的极大子图称为边双连通分量

      • 边双连通分量的特点

        1. 任意一条边至少包含在一个简单环。
        2. 连通分量里没有桥。
        3. 割点只属于一个边双连通分量
        4. 两个边双连通分量最多只有一条边,且必为桥。进一步地,所有边双与桥可抽象为一棵树结构。
      • 边双连通分量里,一个点有可能出现在多个简单环里,所以我们在当前点u的所有子树访问结束,即变黑后,如果dfn[u]==low[u],从栈顶到u的点均为同一边双连通分量,节点u必然是此边双的最早访问的点。

      • code

        void tarjan(int u,int fa){
            bool flag=0;//是否有重边
            low[u]=dfn[u]=++Time;
            st[++Top]=u;//依次进栈
            for(int i=head[u];i;i=e[i].next){
                int v=e[i].to;
                if(!dfn[v]){//白点
                    tarjan(v,u);
                    low[u]=min(low[u],low[v]);//儿子更新父亲
                }
                else if(v!=fa){
                    low[u]=min(low[u],dfn[v]);
                }             
            }  //u的子树全部访问结束,边双缩点
            if(low[u]==dfn[u]){ 
                num++;
                int tmp;
                do{
                    tmp=st[Top--]; //退栈,原来栈中的元素构成一个边双
                    belong[tmp]=num;
                }while(tmp!=u);
            }
        }
        
    2. 点双连通图:如果任意两点至少存在不重复的路径,则称这个图为点双连通的(简称双连通);

      • 点双连通图的定义等价于任意两个都在同一个简单环中。

      • 点双连通分量:点双连通的极大子图称为点双连通分量(简称双连通分量)

      • 点双连通分量的特点

        1. 该连通分量的点在同一简单环
        2. 该连通分量没有桥。
        3. 一个割点可以多个点连通分量。
      • code

        void tarjan(int u,int fa){
            low[u]=dfn[u]=++Time; 
            st[++Top]=u;//依次进栈
            for(int i=head[u];i;i=e[i].next){  
                int v=e[i].to;
                if(!dfn[v]){
                    tarjan(v,u);
                    low[u]=min(low[u],low[v]);
                    if(dfn[u]<=low[v]){//如果u为割点,点双缩点                
                        ++num; //num表示第几个点双区域(一个图可能存在多个点双) 
                        while(st[top+1]!=v){//从栈顶到v依次出栈
                            int w=s[top--];//去栈顶并退栈
                            dcc[num].push_back(w);//节点v属于编号为num的点双
                        }
                        dcc[num].push_back(u);//u可以在多个dcc,所以不出栈
                    }
                }
                else if(v!=fa){
                    low[u]=min(low[u],dfn[v]);
                }
            }
        }
        

4. 强连通分量和双连通分量常见的模型和问法

  • 双连通分量

    1. 有一些点,一些边,加最少的边,要使得整个图变成双联通图。
      • 如果是连通图,先缩点,建图,新图为一颗树,求出叶子节点个数cnt,最后答案为(cnt+1)/2
      • 如果是非连通图,缩点后,先把单点连起来,再来就算叶子个数,或把单点算两个叶子。
    2. 连通图,给一个起点和一个终点,问从起点到终点的必经点。
      • 点双缩点,然后建成树,起点到终点路径上点均为必经点。
  • 强连通分量

    1. 有一些点,一些有向边,求至少加多少边使任意两个点可相互到达
      • 求出所有的分量,缩点,分别求出出度入度0的点的数量,取的为答案;
    2. 有一些点,一些有向边,求在这个图上走一条路最多可以经过多少个点
      • 求出所有的分量,缩点,形成一个或多个DAG图,然后做DAG上的dp
    3. 有一些点,一些有向边,给出一些特殊点,求终点是特殊点的最长的一条路
      • 求出所有分量,并标记哪些分量有特殊点,然后也是DAGdp

5. Tarjan求最大最小环

  • Tarjan算法一般用来强连通分量,它依次访问图中的各个强连通分量,这题要求最大环,而环也是强连通分量的一部分.

  • 在每个点访问其他点时修改时间戳,达到每个环上时间戳连续的目的,这样当访问到一个栈中节点时就能直接更新最大环了。根据同样的思路,即使边权任意,也可求最大环或最小环。

  • code

    void tarjan(int fa,int u){
        dfn[u]=low[u]=++Time;   
        vis[u]=1;s[++top]=u;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(fa==v)continue;
            if(!dfn[v]){
                int tmp=Time;//先记录父节点u的时间戳
                tarjan(u,v);
                Time=tmp;//子树v处理完了,让下一个子树时间戳从Time+1开始
                low[u]=min(low[u],low[v]);  
            }else if(vis[v]==1){//发现返祖边
                low[u]=min(low[u],dfn[v]);
                ans=max(ans,dfn[u]-dfn[v]+1);//环上的点的dfn值是连续的
            }
        }
    
    • 那求最小环如何求?
    • 带权最小环或最大环如何求呢?

原文链接: https://www.cnblogs.com/hbhszxyb/p/12812434.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    Tarjan算法求双连通分量

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/345662

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月2日 上午3:23
下一篇 2023年3月2日 上午3:24

相关推荐