题目链接：?id=19845
大意：有一座地下矿， 有n条隧道相连， 任意两个连接点之间只有一条隧道相连接。 为了降低矿工的危险，， 现在决定在连接点处建一些逃生装置， 使得不管哪个连接点倒塌， 不在此连接点的所有矿工都能逃生。 问安装最少的逃生装置， 及其安装的方案。
分析题可知， 这是求点双联通分量的， 我们只要把只有一个割点的点双联通分量安装一个逃生装置即可。 安装的方案数就是点双联通中节点的个数减去1； 而当只有一个点双联通分量时只需要安装两个逃生装置， 方案数就是v*(v-1)/2;
#include<stdio.h>#include<string.h>#include<vector>#include<stack>#include<algorithm>using namespace std;const int maxn = 100000 + 10;struct Edge{int u, v;Edge(int i, int j) : u(i), v(j) {}};vector<int> G[maxn], bcc[maxn];int low[maxn], dfn[maxn], bccno[maxn];bool iscut[maxn];int cur, cnt;stack<Edge> S; //存边， 就不用处理割点可以同时存在不同的连通分量里了void dfs(int u, int fa){dfn[u] = low[u] = ++cur;int child = 0;for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(v == fa)continue;if(!dfn[v]){S.push(Edge(u, v));child++;dfs(v, u);low[u] = min(low[u], low[v]);if(dfn[u] <= low[v]) //u的子孙后代最早出现的时间不小于u出现的时间， u才能为割点{++cnt;iscut[u] = true;bcc[cnt].clear();while(!S.empty()){Edge x = S.top();S.pop();if(bccno[x.u] != cnt){bcc[cnt].push_back(x.u);bccno[x.u] = cnt;}if(bccno[x.v] != cnt){bcc[cnt].push_back(x.v);bccno[x.v] = cnt;}if(x.u==u && x.v==v)break;}}}else if(dfn[v] < dfn[u]) //关于这个判断为什么不能用强联通和边双联通相同的 bccno[v]==0 判断， 请路过的大牛看到了给解释一下{S.push(Edge(u, v));low[u] = min(low[u], dfn[v]);}}if(fa<0 && child==1) //在起点只有子节点时，起点不是割点iscut[u] = false;}void find_bcc(int n){cur = cnt = 0;memset(dfn, 0, sizeof(dfn));memset(iscut, false, sizeof(iscut));memset(bccno, 0, sizeof(bccno));dfs(1, -1);}int main(){int n, a, b, t = 0;int m = 0;while(scanf("%d", &n), n){for(int i = 0; i <= m; i++)G[i].clear();for(int i = 0; i < n; i++){scanf("%d%d", &a, &b);m = max(m, max(a, b));G[a].push_back(b);G[b].push_back(a);}find_bcc(n);long long ans1 = 0, ans2 = 1;for(int i = 1; i <= cnt; i++){int cnt_cut = 0;for(int j = 0; j < bcc[i].size(); j++){int k = bcc[i][j];if(iscut[k])cnt_cut++;}if(cnt_cut == 1){ans1++;ans2 *= (long long)(bcc[i].size()-cnt_cut);}}if(cnt == 1){ans1 = 2;ans2 = bcc[cnt].size() * (bcc[cnt].size()-1) / 2;}printf("Case %d: %lld %lld\n", ++t, ans1, ans2);}return 0;}
人只要不失去方向，就不会失去自己
