複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/雙連通分量/5339004
複製
複製成功

雙連通分量

鎖定
雙連通分量又分點雙連通分量和邊雙連通分量兩種。若一個無向圖中的去掉任意一個節點（一條邊）都不會改變此圖的連通性，即不存在割點（橋），則稱作點（邊）雙連通圖。一個無向圖中的每一個極大點（邊）雙連通子圖稱作此無向圖的點（邊）雙連通分量。求雙連通分量可用Tarjan算法。
中文名
點（邊）雙連通分量
外文名
Point (Edge) Biconnected Component
定    義
極大點（邊）雙連通子圖
性    質
不存在割點（橋）
相    關
Tarjan算法

目錄

  1. 1 算法
  2. 2 邊雙連通分量
  3. 3 點雙連通分量
  4. 4 代碼
  5. 5 解決實際問題

雙連通分量算法

1. 對圖進行深度優先搜索，計算每一個結點v的深度優先標號dfn[v]。
2. 計算所有結點v的low[v]是在深度優先生成樹上按照後根遍歷的順序進行的。因此，當訪問結點v時它的每個兒子y的low[y]已經計算完畢，這時low[v]取下面三值中最小者：
(1) dfn[v];
(2) dfn[w], 凡是有回退邊(v, w)的任何結點w;
(3) low[y],對v的任何兒子y.
[1] 

雙連通分量邊雙連通分量

若一個無向圖中的去掉任意一條邊都不會改變此圖的連通性，即不存在橋，則稱作邊雙連通圖。一個無向圖中的每一個極大邊雙連通子圖稱作此無向圖的邊雙連通分量。
連接兩個邊雙連通分量的邊即是橋。

雙連通分量點雙連通分量

若一個無向圖中的去掉任意一個節點都不會改變此圖的連通性，即不存在割點，則稱作點雙連通圖。一個無向圖中的每一個極大點雙連通子圖稱作此無向圖的點雙連通分量。
注意一個割點屬於多個點雙連通分量。
為什麼點連通分量必須存邊
這是初學者常見的問題，證明如下：
首先要明確邊雙連通分量和點雙連通分量的區別與聯繫
1.二者都是基於無向圖
2.邊雙連通分量是刪邊後還連通，而後者是刪點
3.點雙連通分量一定是邊雙連通分量（除兩點一線的特殊情況），反之不一定
4.點雙連通分量可以有公共點，而邊雙連通分量不能有公共邊
由於4，顯然，求解邊雙連通分量只需先一遍dfs求橋，在一遍dfs求點（不經過橋即可）
但如果求點雙連通分量，就要更復雜：
1.如果存邊
根據dfs的性質，每條邊都有且只有一次入棧，而由於性質3和性質4，點雙連通分量沒有公共邊，所以彈出這個點雙連通分量裏的所有邊就一定包含這裏面的所有點，而且一定不含其他點雙連通分量的邊。因此求解時只需彈出這個點雙連通分量裏的所有邊，並記錄這些邊的點即可（要判重，一個點可出現多次），正確。
2.如果存點
根據dfs的性質，每個點同樣有且只有一次入棧。但注意，由於性質4，你將一個點出棧後，還可能有別的點雙連通分量包含它，錯誤。
[2] 

雙連通分量代碼

注意：如果圖中有重邊，且允許兩個點形成一個環，則需修改對能否訪問父節點的判斷，即若當前邊指向父節點，但不是從父節點走到當前點的邊，則可以用父節點的dfn更新當前點的low。
邊雙連通分量
#include <cstdio>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repe(i,x) for (edge *i=fst[x]; i; i=i->nxt)
using namespace std;
const int N=100010;
struct edge
{
    int v;
    edge *nxt;
} pool[N<<1],*tp=pool,*fst[N];
int n,m,dfn[N],low[N],st[N],bl[N],tot,idx;
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++idx,st[++*st]=x;
    repe(i,x)
        if (i->v!=fa)
            if (!dfn[i->v])
                tarjan(i->v,x),low[x]=min(low[x],low[i->v]);
            else
                low[x]=min(low[x],dfn[i->v]);
    if (low[x]==dfn[x])
    {
        ++tot;
        do
            bl[st[*st]]=tot;
        while (st[st[0]--]!=x);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        *tp=(edge){v,fst[u]},fst[u]=tp++;
        *tp=(edge){u,fst[v]},fst[v]=tp++;
    }
    rep(i,1,n)
        if (!dfn[i])
            tarjan(i,0);
    printf("%d\n",tot);
    return 0;
}
點雙連通分量
注意：此代碼不會將獨立點記做一個連通分量。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define mem(x,y) memset(x,y,sizeof(x))
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repe(i,x) for (edge *i=x; i; i=i->nxt)

using namespace std;
const int N=200010;
struct edge
{
    int v;
    edge *nxt;
} pool[N<<2],*tp,*fst[N];
int n,m,tot,fct[N],dfn[N],low[N],idx,top;
//fct[i] means whether i is a cutvertex, fct[i]>0 means i is a cutvertex.
vector <int> bl[N];
edge *st[N];

inline void add(int u,int v)
{
    *tp=(edge){v,fst[u]},fst[u]=tp++;
    *tp=(edge){u,fst[v]},fst[v]=tp++;
}

void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++idx;
    repe(i,fst[x])
        if (i->v!=fa)
            if (!dfn[i->v])
            {
                st[++top]=i,tarjan(i->v,x);
                low[x]=min(low[x],low[i->v]);
                if (low[i->v]>=dfn[x])
                {
                    ++fct[x],bl[++tot].clear(),bl[tot].push_back(x);
                    do
                        bl[tot].push_back(st[top]->v);
                    while (st[top--]!=i);
                }
            }
            else
                low[x]=min(low[x],dfn[i->v]);
}

inline void work()
{
    idx=tot=top=0,mem(dfn,0),mem(fct,0);
    rep(i,1,n)
        if (!dfn[i])
            fct[i]=-1,tarjan(i,0);
}

int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    work();
    return 0;
}

雙連通分量解決實際問題

POJ 3177Redundant Paths
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int MAXN=5001,MAXE=20001;
stack <int> s;
int cnt,first[MAXN],low[MAXN],dfn[MAXN],newnode[MAXN],Timetable,node,dgr[MAXN],tot;
struct ARC {
    int go,next,num,self;
    ARC() {
        next=-1;
    }
} arc[MAXE];
void add(int a,int b) {
    arc[++cnt].next=first[a];
    arc[cnt].go=b;
    arc[cnt].num=cnt;
    arc[cnt].self=a;
    first[a]=cnt;
}
void tarjan(int u,int num) {
    s.push(u);
    low[u]=dfn[u]=++Timetable;
    for(int i=first[u]; i!=-1; i=arc[i].next) {
        int v=arc[i].go;
        if((arc[i].num-1)/2!=num) {
            if(!dfn[v]) {
                tarjan(v,(arc[i].num-1)/2);
                low[u]=min(low[u],low[v]);
                if(dfn[v]==low[v]) {
                    int point;
                    node++;
                    do {
                        point=s.top();
                        s.pop();
                        newnode[point]=node;
                    } while(point!=v);
                }
            }            else low[u]=min(low[u],dfn[v]);
        }
    }
}
int main() {
    int t,r;
    scanf("%d %d",&t,&r);
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(newnode,0,sizeof(newnode));
    memset(dgr,0,sizeof(dgr));
    memset(first,-1,sizeof(first));
    for(int i=1; i<=2*r; i++) arc[i].next=-1;
    cnt=Timetable=node=tot=0;
    for(int i=1; i<=r; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=t; i++)
        if(!dfn[i]) {
            tarjan(i,-1);
            node++;
            while(!s.empty())
                newnode[s.top()]=node,s.pop();
        }
    for(int i=1; i<=cnt; i++)
        if(newnode[arc[i].self]!=newnode[arc[i].go])
            dgr[newnode[arc[i].self]]++,dgr[newnode[arc[i].go]]++;
    for(int i=1; i<=node&&node>1; i++)
        if(dgr[i]<=2)
            tot++;
    printf("%d\n",(tot+1)/2);
}
參考資料