无向图边双连通分量+构造双连通图

　　边双连通分量: 边连通度大于1的连通分量

　　在树中至少添加多少边能使得图变为边双连通图 ? 添加的边=(叶子节点+1)/2.

　　在一个无向图中，我们可以把它的边双连通分量缩成一个点，然后一定会得到一颗树，然后按上述方法求叶节点即可。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define _Clr(x, y) memset(x, y, sizeof(x))
  6 #define INF 0x3f3f3f3f
  7 #define N 5010
  8 using namespace std;
  9 
 10 struct Node
 11 {
 12     int to, next;
 13 }edge[N*2];
 14 int head[N], tot;
 15 int dfn[N], low[N];
 16 int bleg[N], Sta[N];
 17 bool instack[N];
 18 int n, cnt, ght, top;
 19 
 20 void Init()
 21 {
 22     cnt=tot=top=ght=0;
 23     _Clr(head, -1);
 24     _Clr(dfn, 0);
 25     _Clr(instack, 0);
 26 }
 27 
 28 void Add_edge(int a, int b)
 29 {
 30     edge[tot].to = b;
 31     edge[tot].next = head[a];
 32     head[a] = tot++;
 33 
 34     edge[tot].to = a;
 35     edge[tot].next = head[b];
 36     head[b] = tot++;
 37 }
 38 
 39 void dfs(int u, int f)
 40 {
 41     dfn[u]=low[u]=++cnt;
 42     instack[u] = true;
 43     Sta[top++] = u;
 44     for(int i=head[u]; i!=-1; i=edge[i].next)
 45     {
 46         int v = edge[i].to;
 47         if(i==(f^1)) continue;
 48         if(!dfn[v])
 49         {
 50             dfs(v, i);
 51             low[u] = min(low[u], low[v]);
 52         }
 53         else if(instack[v]) low[u] = min(low[u], dfn[v]);
 54     }
 55     if(low[u]==dfn[u])
 56     {
 57         ght++;
 58   //      printf("Num:%d
", ght);
 59         while(1)
 60         {
 61             int v = Sta[--top];
 62             bleg[v] = ght;
 63  //           printf("%d ", v);
 64             instack[v] = false;
 65             if(u == v) break;
 66         }
 67    //     puts("");
 68     }
 69 }
 70 
 71 int de[N];
 72 void Tarjan()
 73 {
 74     int ans=0;
 75     dfs(1, -1);
 76     _Clr(de, 0);
 77     for(int u=1; u<=n; u++)
 78     for(int i=head[u]; i!=-1; i=edge[i].next)
 79     {
 80         int v = edge[i].to;
 81         if(bleg[v] != bleg[u]) de[bleg[v]]++;
 82     }
 83     for(int i=1; i<=ght; i++)
 84     {
 85     //    printf("de[%d]=%d 
", i, de[i]);
 86         if(de[i]==1) ans++;
 87     }
 88     printf("%d
",(ans+1)>>1);
 89 }
 90 int main()
 91 {
 92     int m, a, b;
 93     while(~scanf("%d%d", &n, &m))
 94     {
 95         Init();
 96         while(m--)
 97         {
 98             scanf("%d%d", &a, &b);
 99             Add_edge(a, b);
100         }
101         Tarjan();
102     }
103     return 0;
104 }

View Code