在说TarjanTarjan算法解决桥和边双连通分量问题

在说 Tarjan 的算法解决桥接和边双连通分量的问题之前，我们先来回顾一下 Tarjan 的算法是如何解决强连通分量的。

Tarjan的算法在求解强连通分量时，引入了阶dfsNum（即访问该点之前已经访问过的点数）和一个点在dfs过程中可以到达的最小dfsNum的low数组。，当我们遇到一个dfsNum值等于low值的顶点时，那么这个点就是一个强连通分量的根。因为我们在dfs的过程中已经把点入栈了，所以只需要弹出栈中的元素，直到遇到根，那么这些点就形成了一个强连通分量。

对于边双连通组件，我们需要先了解一些概念：

边连通性：使子图断开连接所需的最小边数是图的边连通性。

桥（切边）：删除边时，使图不连贯的边称为桥或切边。

边双连通分量：边连通性大于等于二的子图称为边双连通分量。

了解了这些概念之后，我们来看看 Tarjan 是如何解决边缘双连通组件的，不过在此之前，我们先来说说 Tarjan 是如何找到桥的。还引入了dfsNum来表示dfs过程中某个点被访问的时间，然后低位数组表示该点的最小可达dfsNum。我们来分析一下桥的特点。删除一条边后，如果dfs进程中的子树中没有点可以到达父节点和父节点之上的节点，那么此时子树被阻塞。这条边是桥。有了这个性质，也就是说当我们在dfs过程中遇到一个树边a->b，而此时low[b]>dfsNum[a]，那么ab就是一个桥。

哈哈，桥已经求好了，你还怕双连组件吗？在我们移除所有桥之后，那些独立的组件是不同的边缘双连通组件。这时，我们可以根据需要灵活找到边缘双连通分量。

以下是POJ 3352的解题思路：

这道题的意思是说，给你一个无向图，然后要求你加至少几条边c语言无向图连通分量，使整个图成为边双连通分量，也就是说任意两点至少有两条路径可以相互连接。. 我们这样考虑这个问题，属于同一个边双连通分量的任何点至少有两条相互可达的路径，因此我们可以将一个边双连通分量收缩为一个点。然后考虑不在边的双连通分量中的点，通过这些点后形成一棵树。对于一个树形的无向图，需要添加（度为1+1）/2条边的点的个数，使图双连通。问题是求它之后的图的度数成为一个收缩点。

这道题的条件很强，说明任意两点之间都不会有双边c语言无向图连通分量，所以我们可以直接通过Tarjan的低值来划分边的双连通分量，最后求出1点的度数解决问题。如果有多个边，那么不同的低值可能属于同一个边双连通分量。这时，我们需要去掉图中的桥，然后求解边双连通分量。请参阅我博客的另一部分。问题解决报告。

POJ 3352的ac代码贴在下面，供网友参考：

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int Max=1010;
int top[Max],edge[Max][Max];//memset(top,0,sizeof(top));
int dfsNum[Max],dfsnum;//memset(dfsNum,0,sizeof(dfsNum)),dfsNum=1;
int low[Max];
int degree[Max];
int ans;
void tarjan(int a,int fa)
{
    dfsNum[a]=low[a]=++dfsnum;
    for(int i=0;ilow[edge[a][i]])
                    low[a]=low[edge[a][i]];
            }
            else
            {
                if(low[a]>dfsNum[edge[a][i]])
                    low[a]=dfsNum[edge[a][i]];
            }
  //          if(low[edge[a][i]]>dfsNum[a])
  //          {
   //         }
        }
    }
}
int solve(int n)
{
    int i,j;
    int a,b;
    for(i=1;i
        {
            b=edge[a][j];
            if(low[a]!=low[b])
            {
                degree[low[a]]++;
                degree[low[b]]++;
            }
        }
    }
    int leaves=0;
    for(i=1;i<=n;i++)
    {
        if(degree[i]==2)
        {
            leaves++;
        }
    }
    return (leaves+1)/2;
}
int main()
{
    int n,m;
    int i,a,b;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(top,0,sizeof(top));
        memset(degree,0,sizeof(degree));
        for(i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            edge[a][top[a]++]=b;
            edge[b][top[b]++]=a;
        }
        memset(dfsNum,0,sizeof(dfsNum));
        dfsnum=0;
        tarjan(1,-1);
        ans=solve(n);
        printf("%dn",ans);
    }
    return 0;
}

上面代码的写法确实有问题，因为点在同一个双连通分量中的低值不一定相等，所以用低值来判断它们是否在同一个分量中显然是有问题的. 所以，我们在做菜的时候，在tarjan过程中标记bridge，然后用dfs运行每个连通的组件，最后用bridge统计每个点的度数是最安全的。

对于上述问题的误导，我深表歉意。

下面的代码是对上面代码的修改，分享的有点乱。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int Max=1010;
int top[Max],edge[Max][Max];//memset(top,0,sizeof(top));
int dfsNum[Max],dfsnum;//memset(dfsNum,0,sizeof(dfsNum)),dfsNum=1;
int low[Max];

int degree[Max];
int ans;
bool exist[Max][Max];
void tarjan(int a,int fa)
{
    dfsNum[a]=low[a]=++dfsnum;
    for(int i=0;ilow[edge[a][i]])
                    low[a]=low[edge[a][i]];
                if(dfsNum[a] dfsNum[edge[a][i]])
                    low[a]=dfsNum[edge[a][i]];
            }
        }
    }
}
int cc[Max], ccCnt;
void dfs(int fa, int u)
{
    cc[u] = ccCnt;
    for(int i=0; i<top[u]; i++)
    {
        int v = edge[u][i];
        if(v != fa && !exist[u][v] && !cc[v])
        {
           // printf("v %dn", v);
            dfs(u, v);
        }
    }
}
int solve(int n)
{
    int i,j;
    int a,b;
    memset(cc, 0, sizeof(cc));
    ccCnt = 1;
    for(i=1; i<=n; i++)
    {
        if(!cc[i])
        {

            dfs(-1, i);
            ccCnt++;
        }
    }
    //cout<<"ccCnt "<<ccCnt<<endl;
    for(i=1;i<=n;i++)
    {
        a=i;
        for(j=0;j<top[i];j++)
        {
            b=edge[a][j];
            if(cc[a] != cc[b])
            {
                degree[cc[a]]++;
                degree[cc[b]]++;
            }
        }
    }
    int leaves=0;
    for(i=1;i<ccCnt;i++)
    {
        if(degree[i]==2)
        {
            leaves++;
        }
    }
    return (leaves+1)/2;
}
int main()
{
    int n,m;
    int i,a,b;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(top,0,sizeof(top));
        memset(degree,0,sizeof(degree));
        for(i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            edge[a][top[a]++]=b;
            edge[b][top[b]++]=a;
        }
        memset(dfsNum,0,sizeof(dfsNum));
        dfsnum=0;
        memset(exist, false, sizeof(exist));
        tarjan(1,-1);
        ans=solve(n);
        printf("%dn",ans);
    }
    return 0;
}