POJ 3352 缩点 + 边双连通图

题目链接： http://poj.org/problem?id=3352

题目大意及分析：

　　题目我看了很多遍，没有看懂，关于至少添加多少边使得图双连通我没有想出来怎么做，直接看题解的，附一个好的题解：

　　http://blog.csdn.net/lyy289065406/article/details/6762370

PS：

　　不得不说这题让我对一些概念有更深的理解。

　　本题，只需要保证每两个点之间至少有两条路径，但是求出来的未必是双连通图，比如：

　　5 4

　　1 2

　　2 3

　　2 4

　　2 5

　　结果是2,但是加2条边后不是双连通图。

　　所以这个题解我把标题写成了缩点+ 边双连通图。

　　我们必须要知道有种东西叫：边双连通。

　　我们常说的双连通分量是指不含割点的子图，割边（桥）连接的不一定是双连通分支（分量）。

　　关于最后上面链接提到的那个结论公式，我在Beyond the Void大神博客里找到了一个解释：

统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

代码：

poj3352

 1 /*3352    Accepted    292K    110MS    C++    2205B    2012-06-10 16:59:26*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 
10 #define mpair make_pair
11 #define pii pair<int,int>
12 #define MM(a,b) memset(a,b,sizeof(a));
13 typedef long long lld;
14 typedef unsigned long long u64;
15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
17 #define maxn 1020
18 
19 int n,m;
20 vector<int> adj[maxn];
21 
22 int Bcnt, Index, Top;
23 int low[maxn], dfn[maxn], sta[maxn], belong[maxn];
24 bool vis[maxn];
25 void Init_tarjan(){
26     Bcnt= Index= Top= 0;
27     for(int i=1;i<=n;++i) low[i]= dfn[i]= vis[i]= 0;
28 }
29 void Tarjan(int u,int fa){
30     low[u]= dfn[u]= ++Index;
31     sta[++Top]= u;
32     vis[u]= 1;
33     for(int i=0;i<adj[u].size();++i){
34         int v= adj[u][i];
35         if( v==fa ) continue;
36 
37         if( !dfn[v] ){
38             Tarjan( v, u );
39             up_min( low[u], low[v] );
40         }
41         else if( vis[v] )
42             up_min( low[u], dfn[v] );
43     }
44     if( low[u]==dfn[u] ){
45         ++Bcnt;
46         int v;
47         do{
48             v= sta[Top--];
49             vis[v]= 0;
50             belong[v]= Bcnt;
51         }while( u!=v );
52     }
53 }
54 
55 int degree[maxn];
56 void dfs(int u){
57     vis[u]= 1;
58     for(int i=0;i<adj[u].size();++i){
59         int v= adj[u][i];
60         if( !vis[v] ){
61             if( belong[u]!=belong[v] ){
62                 ++degree[ belong[v] ];
63                 ++degree[ belong[u] ];
64             }
65             dfs(v);
66         }
67     }
68 }
69 
70 int main()
71 {
72     //freopen("poj3352.in","r",stdin);
73     while( cin>>n>>m ){
74         int i,x,y;
75         for(i=1;i<=n;++i) adj[i].clear();
76         while( m-- ){
77             scanf("%d%d", &x, &y);
78             adj[x].push_back(y);
79             adj[y].push_back(x);
80         }
81 
82         Init_tarjan();
83         Tarjan( 1, 1 ); ///
84 
85         if( 1==Bcnt ){
86             puts("0"); continue;
87         }
88 
89         fill( degree, degree+1+Bcnt, 0 );
90         MM( vis, 0 );
91         dfs( 1 );
92 
93         int tot= 0;
94         for(i=1;i<=Bcnt;++i)
95             if( degree[i]==1 ) tot++;
96         printf("%d\n",(tot+1)/2 );
97     }
98 }