一、无向图的割点与桥的基本概念:
   
给定无向连通图G = (V, E)
割点:
对于x∈V,从图中删去节点x以及所有与x关联的边之后,G分裂为两个或两个以上不相连的子图,则称x为割点

割边(桥):
若对于e∈E,从图中删去边e之后,G分裂成两个不相连的子图,则称e为G的桥或割边

一般无向图(不一定连通)的割点与桥就是它的各个连通块的各点和桥

Tarjan算法基于无向图的深度优先遍历。
时间戳
在图的深度优先遍历过程中,按照每个节点第一次被访问的时间顺序,依次给予N个节点1~N的整数标记,该标记被称为“时间戳”,记为dfn[x]

搜索树
在无向连通图中任选一个节点出发进行深度优先遍历吗,每个节点只访问一次。所有发生递归的边(x, y)(换言之,从x到y是对y 的第一次访问)构成一棵树,称为“无向连通图的搜索树”。一般无向图的各个连通块的搜索树构成无向图的“搜索森林”。对于深度优先遍历出的搜索树,按照被遍历的次序,标记节点的时间戳

追溯值
追溯值low[x]。设subtree(x)表示搜索树中以x为根的子树。low[x]定义为以下节点时间戳的最小值
即:
1.subtree(x)中的节点
2.通过一条不在搜索树上的边,能够到达subtree(x)的节点

为了计算low[x],应该先令low[x] = dfn[x],然后考虑从x出发的每条边(x, y):
若在搜索树上x是y的父节点,则令low[x] = min(low[x], low[y])
若无向边(x, y)不是搜索树上的边,则令low[x] = min(low[x], dfn[y])。

   
   
二、割边的判定法则:
无向边(x, y)是桥,当且仅当搜索树上存在x的一个子节点y,满足:

         dfn[x] < low[y]

根据定义,dfn[x] <low[y]说明从subtree(y)出发,在不经过(x, y)的前提下,不管走哪条边,都无法到达x或比x更早访问的节点。若把(x, y)删除,则subtree(y)就好像形成了封闭的环境,与节点x没有边相连,图断成了两部分,(x, y)为桥
反之,若不存在这样的子节点y,使得dfn[x] < low[y],这说明每个subtree(y)都能绕行其他边到x或比x更早的节点,(x, y)也就不是桥

桥一定是搜索树中的边,并且一个简单环中的边一定都不是桥

   需要注意的是, 因为我们要遍历的是无向图, 所以从每个节点x出发,总能访问到他的父节点fa,根据low的计算方法,(x, fa)属于搜索树上的边,且fa不是x的子节点,故不能用fa的时间戳来更新low[x]。

   但是,如果仅记录每个节点的父节点,会无法处理重边的情况——当x与fa之间有多条边时,(x, fa)一定不是桥,在这些重复计算中,只有一条边在搜索树上,其他的几条都不算,故有重边时,dfn[fa]能用来更新low[x]

   解决方案是:记录“递归进入每个节点的边的编号”。编号可认为是边在邻接表中储存下标位置。把无向图的每条边看做双向边,成对存储在下标"2和3",“4和5”,“6和7”…处。若沿着编号i的边递归进入节点x,则忽略从x出发的编号为i xor 1的边,通过其他边计算low[x]即可

下面的程序求出一张无向图中所有的桥。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100010;
int head[maxn],ver[maxn*2],nt[maxn*2];
int dfn[maxn],low[maxn],n,m,tot,num=0;
bool bridge[maxn*2];

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void tarjan(int x,int in_edge)
{
    dfn[x] = low[x] = ++num;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);

            if(low[y]>dfn[x])
                bridge[i]=bridge[i^1] =true;
        }
        else if(i != (in_edge^1))
            low[x]=min(low[x],dfn[y]);
    }
}

int main(void)
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i,0);
    }

    for(int i=2;i<tot;i+=2)
        if(bridge[i]) printf("%d %d \n",ver[i^1],ver[i]);

    return 0;
}

   
   
   
三、割点判定法则:

若x不是搜索树的根节点(深度优先遍历的起点),则x是割点当且仅当搜索树上存在x的一个子节点y,满足:
    dfn[x] <= low[y]
特别地,若x是搜索树的根节点,则x是割点当且仅当搜索树上存在至少两个子节点y1, y2满足上述条件

下面的程序求出一张无向图中所有的割点。
割点判定的符号为小于等于号,不必再考虑父节点和重边的问题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100010;
int head[maxn],ver[maxn*2],nt[maxn*2];
int dfn[maxn],low[maxn],st[maxn];
int root,n,m,tot,num=0;
bool cut[maxn];

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    int flag=0;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x])
            {
                flag++;
                if(x != root ||flag>1) cut[x]=true;
            }
        }
        else
            low[x]=min(low[x],dfn[y]);
    }
}

int main(void)
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y) continue;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) root=i,tarjan(i);
    }

    for(int i=1;i<=n;i++)
        if(cut[i]) printf("%d\n",i);

        puts("are cut-vertexes\n");

    return 0;
}

例题:HYSBZ - 1123 BLO
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。

Input
输入n<=100000 m<=500000及m条边

Output
输出n个数,代表如果把第i个点去掉,将有多少对点不能互通。

Sample Input
5 5
1 2
2 3
1 3
3 4
4 5
Sample Output
8
8
16
14
8
感觉题意有点偏差,应该是把与节点i相连的边都去掉之后(不去掉节点i本身),无向图中有多少个有序点对(x,y)满足x和y不连通。

对于询问的节点i,可能有两种情况
1.i不是割点
2.i是割点

若i不是割点,则将i以及与i有直接相连的边删去后,图分为了i和其他节点这两个部分
即:i被孤立出来了
此时对于不能与i联通的点的个数为n-1,即有n-1个点不能与i相互到达。
因为题目求的是有序点对,也就是说,例如(1, 2)和(2, 1),这是不同的点对。
所以若i不是割点,则答案为2*(n-1)

若i是割点,则删去i以及所有与i相连的边后,图会分成若干个连通块。
最后的答案很显然,我们应该求出这些连通块的大小,两两相乘再相加
在图的连通性问题中,我们经常要从搜索树的角度来进行分析。
设在搜索树上,节点i的子节点集合中,有t割点s1,s2,s3…st满足割点判定法则dfn[i] <= low[sk]。于是删除i关联的所有边后无向图至多分成t+2个连通块
每个连通块的节点构成情况为:
1.节点i自身单独构成一个连通块
2.有t个连通块,分别由搜索树上以sk(1 <= k <= t)为根的子树中的节点构成
3.还可能有一个连通块,由除了上述节点以外的所有点构成。
(第三点,即虽然与i相连通,但i不作为搜索树的根。因为整个图是连通的,在不删掉任何一个点时,搜索树只有一个点为根,删掉与i直接相连的边,则被分开的是i,i的子树和i的父亲所在了连通块)

那么可以在tarjan算法执行深度优先遍历的过程中,顺便求出搜索树每棵“子树”的大小,设size[x]表示已x为根的子树的大小。
综上所述,删掉一个割点i之后,不连通的有序对数量为:
设sum = size[s1]+size[s2]+…+size[t-1]+size[t]

ans=size[s1] * (n-size[s1])+size[s2] * (n-size[s2])+…+size[st] * (n-size[st])+1 * (n-1)+(n-1-sum) *(1+sum)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100010,_maxn=500010;
int head[maxn],ver[_maxn*2],nt[_maxn*2];
int dfn[maxn],low[maxn],si[maxn];
ll ans[maxn];
bool cut[maxn];
int n,m,tot,num=0;
void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    si[x]=1;
    int flag=0;
    int sum=0;

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            si[x]+=si[y];
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                flag++;
                ans[x]+=(ll)si[y]*(n-si[y]);
                sum+=si[y];
                if(x!=1||flag>1) cut[x]=true;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(cut[x]) ans[x]+=(ll)(n-sum-1)*(sum+1)+(n-1);
    else ans[x]=2*(n-1);
}

int main(void)
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y) continue;
        add(x,y);
        add(y,x);
    }
    tarjan(1);
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);

    return 0;
}

   
   
   

四、无向图的双连通分量:
若一张无向连通图不存在割点,则我们称它为 点双连通图
若一张无向连通图不存在桥,则我们称它为 边双连通图。

无向图的极大 点双连通子图称为“点双连通分量”,简记为“v-DCC”。
无向连通图的极大 边双连通图称为“边双连通分量”,简记为“e-DCC”
二者统称为“双连通分量”,简记为“BCC”

以下≤意为包含于
在上面的定义中,我们称一个双连通子图K(M,N)极大,M≤V,N≤E。
是指不存在包含K的更大的子图P(Q,T),满足M≤Q≤V,N≤T≤E。并且P也是双联通子图。
(简单来说,极大双连通子图,就是不存在一个包含此双连通子图的更大的双连通子图)。

定理:
一张无向连通图是“点双连通图”,当且仅当满足下列两个条件之一:
1.图的顶点不超过2
2.图中任意两点都同时包含在至少一个简单环中。其中,简单环指的是不自交的环。

一张无向连通图是“边双连通图”,当且仅当任意一条边都包含在至少一个简单环中
   
   
   
五、边双连通分量(e-DCC)的求法:

边双连通分量的计算非常简单,只需要求出无向图中所有的桥,将桥删除后,图会分成若干块,每一个连通块都是一个“边双连通分量”

在具体的程序实现中,一般先用tarjan算法标记出所有的桥边。然后再对整个无向图执行一次深度优先遍历(遍历的过程中不访问),划分出每个连通块。

下面的代码在tarjan求桥的参考程序基础上,计算出数组c,c(x)表示节点x所属的边双连通分量的编号。

int c[maxn],dcc;
void dfs(int x)
{
    c[x]=dcc;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(c[y]||bridge[i]) continue;
        dfs(y);
    }
}

//以下代码在main函数中

for(int i=1;i<=n;i++)
{
    if(!c[i])
    {
        ++dcc;
        dfs(i);
    }
}

printf("There are %d e-DCCs.\n",dcc);

for(int i=1;i<=n;i++)
{
    printf("%d belongs to DCC %d.\n",i,c[i]);
}

e-DCC缩点:
   把每个e-DCC看作一个节点,把桥边(x, y)看做连接编号为c[x]和c[y]的e-DCC对应节点的无向边,会产生一棵树(若原来的无向图不连通,则产生森林)。这种把e-DCC收缩为一个节点的方法称为“缩点”。
   下面的代码在Tarjan求桥、求e-DCC的参考程序的基础上,把e-BCC缩点,构成一棵新的树或者森林,存储在另一个邻接表中。

   
   

int hc[maxn],vc[maxn],nc[maxn];
int tc;

void add_c(int x,int y)
{
    vc[++tc]=y;
    nc[tc]=hc[x];
    hc[x]=tc;
}

//以下代码加在main函数中

tc=1;
for(int i=2;i<=tot;i++)
{
    int x=ver[i^1],y=ver[i];
    if(c[x]==c[y]) continue;
    add_c(c[x],c[y]);
}

printf("缩点之后的森林,点数%d,边数%d(可能有重边)\n",dcc,tc/2);

for(int i=2;i<tc;i+=2)
{
    printf("%d %d\n",vc[i^1],vc[i]);
}

六、点双连通分量(v-DCC)的求法:
   点双连通分量是一个极其容易误解的概念。它与前面的例题BLO中删除割点后图中剩余的连通块是不一样的。

   若某个节点是孤立点,则它自己构成一个v-BCC。除了孤立点外,点双连通分量的大小至少为2。根据v-DCC定义的极大性,虽然桥不属于任何e-DCC,但是割点可能属于多个v-DCC。

   为了求出“点双连通分量”,需要在tarjan算法的过程中维护一个栈,并按照如下方式维护栈中元素:
1.当一个节点第一次被访问时,把该节点入栈
2.当割点判定法则中的条件dfn[x] <= low[y]成立时,无论x是否为根,都需要:
   (1)从栈顶不断弹出节点,直至节点y被弹出
   (2)刚才弹出的所有节点与节点x一起构成一个v-DCC

   
下面的程序在求出割点的同时,计算出vector数组dcc,dcc(i)保存编号为i的v-DCC中所有的节点。

void tarjan(int x)
{
    dfn[x]=low[x]=++sum;
    st[++top]=x;
    if(x==root && head[x]==0)//孤立点
    {
        dcc[++cnt].push_back(x);
        return ;
    }
    
    int flag=0;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                flag++;
                if(x!=root||flag>1) cut[x]=true;
                cnt++;
                int z;
                do
                {
                    z=st[top--];
                    dcc[cnt].push_back(z);
                }while(z!=y);
                dcc[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

//以下代码片段加在main函数中

for(int i=1;i<=cnt;i++)
{
    printf("v-DCC #%d:",i);
    for(int j=0;j<dcc[i].size();j++)
        printf(" %d",dcc[i][j]);
    
    putchar('\n');
}

v-DCC缩点:
   v-DCC的缩点要比e-DCC的缩点复杂一些——因为一个割点可能属于多个v-DCC。
   设图中有p个割点和t个v-DCC,我们建立一张包含p+t个节点的新图,把每个v-BCC和每个割点都作为新图中的节点,并在每个割点与包含它的所有v-BCC之间连边。

这张图就变成了一棵树或是一片森林。

下面的代码在Tarjan求割点和v-DCC的参考程序的main函数基础上,对v-DCC缩点,构成一棵新的树或者森林,存储在另一张链表中。

//给每个割点一个新的编号(编号从cnt+1开始)

num=cnt;

for(int i=1;i<=n;i++)
    if(cut[i]) new_id[i]=++num;

//新建图,从每个v-DCC到它所包含的所有割点连边

tc=1;
for(int i=1;i<=cnt;i++)
{
    for(int j=0;j<dcc[i].size();j++)
    {
        int x=dcc[i][j];
        if(cut[x])
        {
            add_c(i,new_id[x]);
            add_c(new_id[x],i);
        }
        else c[x]=i;
        //除割点外,其他点仅属于一个v-DCC
        
    }
}
printf("缩点之后的森林,点数%d,边数%d\n",num,tc/2);

printf("编号1--%d的为原图的v-DCC,编号>%d的为原图割点\n",cnt,cnt);

for(int i=2;i<tc;i+=2)
    printf("%d %d \n",vc[i^1],vc[i]);

   
   
   
七、例题:
POJ3694 Network。
AcWing 397 逃不掉的路: 边双连通分量,缩点,无向图必经边。
HDOJ 3686 Traffic Real Time Query System: