无向图的双连通分量

双连通分量

点_双连通分量 BCC
　　对于一个连通图,如果任意两点至少存在两条“点不重复”的路径,则说图是点双连通的（即任意两条边都在一个简单环中）,点双连通的极大子图称为点_双连通分量。 通常来说,如果要求任意两条边在同一个简单环中,那么就是求点-双连通
　　易知每条边属于一个连通分量，且连通分量之间最多有一个公共点，且一定是割顶。

#include <cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=10010;
vector<int> graph[MAXN];
int dfn[MAXN];//第一次访问的时间戳
int clocks;//时间戳
int isCut[MAXN];//标记节点是否为割顶
struct Edge
{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
};
vector<Edge> edge;//DFS访问过的边
vector<int> bcc[MAXN];//点_双连通分量
int bccno[MAXN];//节点属于的点_双连通分量的编号
int bcc_cnt;//点_双连通分量的数目
int DFS(int u,int fa)
{
    int lowu=dfn[u]=++clocks;
    int child=0;
    for(int i=0;i<graph[u].size();i++)
    {
        int v=graph[u][i];
        Edge e(u,v);
        if(dfn[v]==0)
        {
            edge.push_back(e);
            child++;
            int lowv=DFS(v,u);
            lowu=min(lowv,lowu);//用后代更新lowu
            if(lowv>=dfn[u])//找到了一个子树满足割顶的条件
            {
                isCut[u]=1;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                while(true)//保存bcc信息
                {
                    Edge ee=edge.back();
                    edge.pop_back();
                    //bccno[ee.u]!=bcc_cnt是为了防止重复加点
                    if(bccno[ee.u]!=bcc_cnt) { bcc[bcc_cnt].push_back(ee.u); bccno[ee.u]=bcc_cnt;}
                    if(bccno[ee.v]!=bcc_cnt) {bcc[bcc_cnt].push_back(ee.v);bccno[ee.v]=bcc_cnt;}
                    if(ee.u==u&&ee.v==v) break;
                }
            }
        }
        else if(dfn[v]<dfn[u]&&v!=fa) //用反向边更新lowu
        {
            edge.push_back(e);
            lowu=min(lowu,dfn[v]);
        }
    }
    if(fa<0&&child==1) isCut[u]=0;
    return lowu;
}
void tarjan(int n)
{
    bcc_cnt=clocks=0;
    memset(dfn,0,sizeof(dfn));
    memset(isCut,0,sizeof(isCut));
    memset(bccno,0,sizeof(bccno));
    memset(bcc,0,sizeof(bcc));
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            DFS(i,-1);
        }
    }
    for(int i=1;i<=bcc_cnt;i++)
    {
        for(int j=0;j<bcc[i].size();j++)
        {
            printf("%d  ",bcc[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(graph,0,sizeof(graph));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        tarjan(n);
    }
}

边_双连通分量 EBC
　　边双连通分量是指任意两点存在至少两条"边不重复"的路径的图,还可以理解为每条边都至少在一个简单环,即每条边都不是桥。如果要求某条边被删除了,但是图G能够在删除任意一条边后，仍然是连通的，当且仅当图G至少为双连通的。
　　对于边双连通分量的求解简单多了，我们先找出所有的桥，并将其做上标记。然后在利用dfs遍历连通分量，只需在遍历时不访问桥即可。

  #include<cstdio>
  #include<cstring>
  #include<algorithm>
  using namespace std;
  const int MAXN=1010;
  const int MAXE=2010;
  struct Node
  {
      int to,next;
      bool cut;//边是否为桥
  };
  Node edge[MAXE];
  int head[MAXN];
  int cnt;
  int dfn[MAXN];
  int low[MAXN];
  int clocks;
  int belong[MAXN];//点属于哪个边连通分量
  int blocks;//连通分量数
  void addEdge(int u,int v)
  {
      edge[cnt].to=v;
      edge[cnt].next=head[u];
      edge[cnt].cut=false;
      head[u]=cnt++;
  }
  //e是为了去重,e是边在数组的位置
  //另一种去重为DFS(u,fa),v!=fa,但是有重边时可能会判断错误
  //比如没重边时,假设(a,b)是桥,但是如果(a,b)有重边,那么(a,b)就不是桥了
  void DFS(int u,int e)//求出所有的桥
  {
    low[u]=dfn[u]=++clocks;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(i==(e^1)) continue;//这里只会去重该边的反边,不会去它的重边
        if(dfn[v]==0)
        {
            DFS(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                edge[i].cut=1;
                edge[i^1].cut=1;
            }
        }
        else if(dfn[v]<dfn[u])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
  }
  void DFS2(int u)//求出每个点所在的边连通分量
  {
      dfn[u]=1;
      belong[u]=blocks;
      for(int i=head[u];i!=-1;i=edge[i].next)
      {
          if(edge[i].cut) continue;
          if(dfn[edge[i].to]==0) DFS2(edge[i].to);
      }
  }
  void work(int n)
  {
      memset(dfn,0,sizeof(dfn));
      memset(belong,0,sizeof(belong));
      clocks=blocks=0;
      for(int i=1;i<=n;i++)
      {
          if(dfn[i]==0)
          {
              DFS(i,-1);
          }
      }
      memset(dfn,0,sizeof(dfn));
      for(int i=1;i<=n;i++)
      {
          if(dfn[i]==0)
          {
              blocks++;
              DFS2(i);
          }
      }
  }
  int main()
  {
     int n,m,a,b;
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         memset(head,-1,sizeof(head));
         cnt=0;
         for(int i=0;i<m;i++)
         {
             scanf("%d%d",&a,&b);
             addEdge(a,b);
             addEdge(b,a);
         }
         work(n);
      }
    }

还有一种办法是栈模拟,直接在DFS里面求出边连通分量,基于一个这样的事实,桥的端点的dfn[u]=low[u]
简要证明以下:
low[u]表示u及其后代能连回的最早的祖先的dfn值,所以low[u]<=dfn[u]总是成立。假设对于桥的一个端点u,low[u]!=dfn[u],即low[u]<dfn[u],说明u可以连到u的父节点或者u通过u的某个子节点通过返祖边连到u的父节点,现在删除这个桥,但是u还可以连接到u的父节点或者u通过u的子代通过返祖边连回到u的父节点,根据桥的性质,删除了桥后u与u的父节点不能连通,这与桥的性质有矛盾,所以假设不成立,即low[u]==dfn[u]

     #include<cstdio>
     #include<stack>
     #include<cstring>
     using namespace std;
     const int MAXN=1010;
     const int MAXE=2010;
     struct Node
     {
         int to,next;
         bool cut;
     };
     Node edge[MAXE];
     int head[MAXN];
     int low[MAXN],dfn[MAXN],onStack[MAXN];
     int cnt,clocks;
     stack<int> sta;
     int belong[MAXN];
     int blocks;
     void addEdge(int u,int v)
     {
         edge[cnt].to=v;
         edge[cnt].next=head[u];
         edge[cnt].cut=false;
         head[u]=cnt++;
     }
     void DFS(int u,int e)
     {
        low[u]=dfn[u]=++clocks;
        onStack[u]=1;
        sta.push(u);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(e==(i^1)) continue;
            if(dfn[v]==0)
            {
                DFS(v,i);
                low[u]=min(low[u],low[v]);
                if(low[v]>dfn[u])
                {
                    edge[i].cut=true;
                    edge[i^1].cut=true;
                }
            }
            else if(onStack[v]&&dfn[v]<dfn[u])//v在栈中，说明(u,v)是返祖边
            {
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(dfn[u]==low[u])//说明u是桥的端点,所以将u所在的边连通分量出栈
        {
            blocks++;
            while(true)
            {
                int curr=sta.top();
                sta.pop();
                onStack[curr]=0;//出栈
                belong[curr]=blocks;
                if(curr==u) break;
            }
        }
     }
     void work(int n)
     {
         memset(dfn,0,sizeof(dfn));
         memset(onStack,0,sizeof(onStack));
         clocks=0;
         while(!sta.empty()) sta.pop();
         memset(belong,0,sizeof(belong));
         blocks=0;
         for(int i=1;i<=n;i++)
         {
             if(dfn[i]==0)
             {
                 DFS(i,-1);
             }
         }
     }
     int main()
     {
         int n,m,a,b;
         while(scanf("%d%d",&n,&m)!=EOF)
         {
             memset(head,-1,sizeof(head));
             cnt=0;
             for(int i=0;i<m;i++)
             {
                 scanf("%d%d",&a,&b);
                 addEdge(a,b);
                 addEdge(b,a);
             }
             work(n);
         }
     }
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 图算法（一）遍历，拓扑排序
    本文介绍图的几种基本操作：BFS，DFS，求有向图连通分量的Tarjan算法以及拓扑排序。 图的表示 一张图是由若...
    maxkibble阅读 3,485评论 0赞 2
  • 强连通算法
    前言：我们伟大的BAT承载了多少程序员的梦想，到底有多少人的向往... 然而这个“T”的面试也是经常不走寻常路，最...
    Tel_小超阅读 1,143评论 0赞 0
  • 简单图论算法笔记
    深度优先搜索 在图中搜索的一般过程为： 记录当前结点被发现的时间(discovery time) 遍历访问未被访问...
    njzwj阅读 1,796评论 0赞 0
  • 聂耳音乐广场
    在520那天我们去师院表演，因为时间有点晚已经没有公交车就打了滴滴，路上和司机聊起了玉溪的夜景，司机很兴奋的提到了...
    春春春春节阅读 1,229评论 0赞 0
  • 20170517   一个人也活的好好的
    今天去参加了“互联网＋创新创业”比赛的培训，去了才发现那么大个阶梯教室人都差不多坐满了，原本以为会没多少人去啊。...
    lanlana阅读 168评论 0赞 0