[LA 5135][WF2011]Mining Your Own Business
转载请注明出处：http://danihao123.is-programmer.com/
点双开坑……
考虑每个点双。如果一个点双有一个（全局的）割点，那么必须要在该点双的一个非割点处建一个出口（否则割掉这个割点会出事）。如果一个点双的割点多于一个，那么其实并没有必要在这里建出口，因为不管割掉那个点，这个点双里面的点总有办法走到一个只有一个割点的点双里。
有一种特殊情况……就是整个图是点双联通的，这样的话随便找两个点建出口就行了。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <utility>#include <vector>#include <stack>#include <map>const int maxn = 100005;std::vector<int> G[maxn];int n;void clear_graph() { for(int i = 1; i <= 100000; i ++) { G[i].clear(); }}void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u);}std::map<int, int> ma;int sz;int trace(int x) { if(ma.count(x)) { return ma[x]; } else { ma[x] = ++ sz; return sz; }}using Edge = std::pair<int, int>;int dcnt, bcc_cnt;int pre[maxn];bool is_cut[maxn]; int bccno[maxn];std::vector<int> bcc[maxn];std::stack<Edge> S;int dfs(int x, int fa = -1) { pre[x] = ++ dcnt; int low = pre[x]; int cld = 0; for(auto v : G[x]) { Edge e = std::make_pair(x, v); if(!pre[v]) { S.push(e); cld ++; int lowv = dfs(v, x); low = std::min(low, lowv); if(lowv >= pre[x]) { is_cut[x] = true; bcc_cnt ++; bcc[bcc_cnt].clear(); while(true) { Edge ee = S.top(); S.pop(); int f = ee.first, g = ee.second; if(bccno[f] != bcc_cnt) { bccno[f] = bcc_cnt; bcc[bcc_cnt].push_back(f); } if(bccno[g] != bcc_cnt) { bccno[g] = bcc_cnt; bcc[bcc_cnt].push_back(g); } if(f == x && g == v) break; } } } else if(pre[v] < pre[x] && v != fa) { S.push(e); low = std::min(low, pre[v]); } } if(fa < 0 && cld == 1) is_cut[x] = false; return low;}void calc_bcc() { std::fill(pre, pre + 1 + sz, 0); std::fill(is_cut, is_cut + 1 + sz, false); std::fill(bccno, bccno + 1 + sz, 0); dcnt = bcc_cnt = 0; for(int i = 1; i <= sz; i ++) { if(!pre[i]) dfs(i); }}using ll = long long;int main() { int cs = 0; while(scanf("%d", &n) == 1) { if(n == 0) break; cs ++; sz = 0; ma.clear(); clear_graph(); for(int i = 1; i <= n; i ++) { int u, v; scanf("%d%d", &u, &v); u = trace(u); v = trace(v); add_edge(u, v); } calc_bcc(); ll a1 = 0, a2 = 1LL; for(int i = 1; i <= bcc_cnt; i ++) { int cnum = 0; for(auto x : bcc[i]) { if(is_cut[x]) cnum ++; } if(cnum == 1) { a1 ++; a2 *= (ll(bcc[i].size() - 1)); } } if(bcc_cnt == 1) { a1 = 2; ll s = bcc[1].size(); a2 = s * (s - 1LL) / 2LL; } printf("Case %d: %lld %lld\n", cs, a1, a2); } return 0;} |
评论 (0)
