poj 3177 poj 3352 (边双连通分支)

题意:告诉你一张无向图,问你构造边双连通分支,需要加最小的边。

思路:发现这两道题可以用一份代码过掉0.0。真是搞笑,题目意思基本相同。主要就是知道如何构造边双连通分支,原来的双连通分支数记为n那么ans = (n+1)/2这个结论是可以证明的。这里我们就把他记住就好了。至于题目的做法就是统计边双连通分支数,直接上模版。

代码如下:

poj 3177 poj 3352 (边双连通分支)
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <stack>
 9 #include <vector>
10 #include <map>
11 #define MP(a, b) make_pair(a, b)
12 #define PB(a) push_back(a)
13 
14 using namespace std;
15 
16 typedef long long ll;
17 typedef pair<int ,int> pii;
18 typedef pair<unsigned int, unsigned int> puu;
19 typedef pair<int ,double> pid;
20 typedef pair<ll, int> pli;
21 
22 const int INF = 0x3f3f3f3f;
23 const int maxn = 2010;
24 const double eps = 1e-6;
25 const int LEN = 1010;
26 vector<pii> Map[LEN];
27 stack<int> s;
28 int n, m, dclock, low[LEN], dfn[LEN], bri[LEN][2], nbri, block, blong[LEN], ind[LEN];
29 
30 void init()
31 {
32     memset(dfn, -1, sizeof dfn);
33     dclock = 1;nbri = block = 0;
34     while(!s.empty())s.pop();
35 }
36 
37 void dfs(int u, int fa){
38     int v;
39     dfn[u] = low[u] = dclock++;
40     s.push(u);
41     for(int i=0; i<Map[u].size(); i++){
42         v = Map[u][i].first;
43         if(v==fa)continue;
44         if(dfn[v]<0){
45             dfs(v, u);
46             low[u] = min(low[u], low[v]);
47             if(low[v] > dfn[u]){
48                 Map[u][i].second = 1;
49             }
50         }else if(low[u]>low[v]) low[u] = min(low[u], dfn[v]);
51     }
52     if(low[u] == dfn[u]){
53         block ++;
54         do{
55             v = s.top(); s.pop();
56             blong[v] = block;
57         }while(v!=u);
58     }
59 }
60 
61 int main()
62 {
63 //    freopen("in.txt", "r", stdin);
64 
65     int a, b;
66     map<int, int> mp;
67     while(scanf("%d%d", &n, &m)!=EOF){
68         for(int i=0; i<LEN; i++)Map[i].clear();
69         for(int i=0; i<m; i++){
70             scanf("%d%d", &a, &b);
71             if(mp.count(a*maxn+b))continue;
72             mp[a*maxn+b] = mp[b*maxn+a] = 1;
73             Map[a].PB(MP(b, 0));
74             Map[b].PB(MP(a, 0));
75         }
76         init();
77         dfs(1, -1);
78         int ans = 0;
79         //缩点统计度数 由于是无向图所以度数是实际两倍
80         memset(ind, 0, sizeof ind);
81         for(int i=1; i<=n; i++){
82             for(int j=0; j<Map[i].size(); j++){
83                 int a = i, b = Map[i][j].first;
84                 if(blong[a]==blong[b])continue;
85                 ind[blong[a]]++;
86             }
87         }
88 
89         for(int i=1; i<=block; i++)if(ind[i]==1)ans++;
90         ans = (ans+1)/2;    //公式
91         printf("%d\n", ans);
92     }
93     return 0;
94 }
View Code

poj 3177 poj 3352 (边双连通分支)

上一篇:浮动闭合方案:clearfix


下一篇:解Bug之路-中间件"SQL重复执行"