poj 3353 Road Construction tarjan 边双联通分支缩点+结论

题意：一个连通的无向图，求至少需要添加几条边，救能保证删除任意一条边，图仍然是连通的。

思路：边的双连通图。其实就是要求至少添加几条边，可以使整个图成为一个边双连通图。用tarjan算法(求割点割边)求出low数组，这里可以简化，然后依据“low相同的点在一个边连通分量中”，缩点之后构造成树(这里可以直接利用low[]数组，low[i]即为第i节点所在的连通分量的标号)。求出树中出度为1的节点数left，答案即为(leaf+1)/2。

代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <stdlib.h>
  6 #include <vector>
  7 #include <queue>
  8 #include <stack>
  9 #define loop(s,i,n) for(i = s;i < n;i++)
 10 #define cl(a,b) memset(a,b,sizeof(a))
 11 const int maxn = 1005;
 12 using namespace std;
 13 int dfn[maxn],low[maxn],belong[maxn],dfsclock,bcc_cnt;
 14 vector<int>g[maxn];
 15 vector<int>ng[maxn];
 16 struct edge
 17 {
 18     int u,v,w;
 19 };
 20 stack<edge> st;
 21 vector<edge> edges;
 22 stack<int>s;
 23 void init(int n)
 24 {
 25     int i;
 26     for(i = 0; i <= n; i++)
 27         g[i].clear();
 28     edges.clear();
 29     return ;
 30 }
 31 int in[maxn];
 32 void tarjan(int u,int pre)
 33 {
 34     int v,i,j;
 35     dfn[u] = low[u] = ++dfsclock;
 36     s.push(u);
 37     loop(0,i,g[u].size())
 38     {
 39         v = g[u][i];
 40 
 41         if(v != pre)
 42         {
 43             if(!dfn[v])//保证是树枝边
 44             {
 45                 tarjan(v,u);
 46 
 47                 low[u] = min(low[v],low[u]);
 48 
 49             }
 50             else if(dfn[v] < low[u])
 51             low[u] = dfn[v];
 52         }
 53 
 54     }
 55     if(low[u] ==dfn[u])
 56     {
 57         bcc_cnt++;
 58         int t;
 59         do
 60         {
 61 
 62             t = s.top();
 63             s.pop();
 64             belong[t] = bcc_cnt;
 65         }
 66         while(t != u);
 67     }
 68 }
 69 
 70 
 71 void find_bcc(int n)
 72 {
 73     int i;
 74     memset(dfn,0,sizeof(dfn));
 75     memset(low,0,sizeof(low));
 76 
 77     memset(belong,0,sizeof(belong));
 78     while(!s.empty())s.pop();
 79     dfsclock = bcc_cnt = 0;
 80     loop(1,i,n)
 81     if(!dfn[i]) tarjan(i,-1);
 82     // puts("yes");
 83     // printf("%d  """"""
",bcc_cnt);
 84 }
 85 
 86 int main()
 87 {
 88     int m,n;
 89    
 90     while(~scanf("%d %d",&n,&m))
 91     {
 92         init(n);
 93         int i,j;
 94         for(i = 1; i <= m; i++)
 95         {
 96             int u,v;
 97             struct edge e;
 98             scanf("%d %d",&u,&v);
 99             g[u].push_back(v);
100             g[v].push_back(u);
101             e.u = u;
102             e.v = v;
103             edges.push_back(e);
104         }
105 
106         find_bcc(n);
107         cl(in,0);
108         struct edge e;
109         for(j = 0; j < edges.size(); j++)
110         {
111             e = edges[j];
112             if(belong[e.v] != belong[e.u])
113             {
114                 in[belong[e.v]]++;
115                 in[belong[e.u]]++;
116             }
117         }
118         int leaf;
119         leaf = 0;
120        // cout<<bcc_cnt<<endl;
121         for(i = 1; i <= bcc_cnt; i++)
122             if(in[i]==1)
123                 leaf++;
124 
125         cout<<(leaf+1)/2<<endl;
126     }
127     return 0;
128 }

View Code

poj 3353 Road Construction tarjan 边双联通分支 缩点+结论

poj 3353 Road Construction tarjan 边双联通分支缩点+结论