题目链接

solution：

1.如果没有割顶，则只需两个太平井。

2.如果有割顶，则在每一个割顶数为一的双联通分量上装一个太平井。

#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 5e4 + 7;vector<int> G[N], bcc[N]; 
int bcc_cnt=0;struct Edge{Edge() {}Edge(int x, int y) {u = x; v = y;}int u, v;
};stack<Edge> S;int dfn[N], id=0, pos[N], iscut[N];
int n, tmp;int dfs(int u, int fa) {int lowu = dfn[u] = ++id;int child = 0;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i]; Edge e(u, v); if (!dfn[v]) {S.push(e);child++;int lowv = dfs(v, u);lowu = min(lowu, lowv);if (lowv >= dfn[u]) {iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear();for (;;) {Edge x = S.top(); S.pop(); if (pos[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u);pos[x.u] = bcc_cnt;}if (pos[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v);pos[x.v] = bcc_cnt;}if (x.u == u && x.v == v) break;}}}else if (dfn[v] < dfn[u] && v != fa) {S.push(e); lowu = min(lowu, dfn[v]);}}if (fa < 0 && child == 1) iscut[u] = 0;return lowu;
}void find_bcc(int n){memset(dfn,0,sizeof(dfn));memset(pos,0,sizeof(pos));memset(iscut,0,sizeof(iscut));bcc_cnt=id=0;for ( int i=1; i<=n; i++ ) if( !dfn[i] ) dfs(i,-1);
}
int main(){int n, kase=0, m;while( ~scanf("%d", &n ) & n ){for ( int i=0; i<=N; i++ ) G[i].clear();tmp=0;for ( int i=1; i<=n; i++ ){int x, y;//x=read(), y=read();cin>>x>>y; tmp=max(tmp, max(x,y ) );G[x].push_back(y);G[y].push_back(x);}find_bcc(tmp);long long ans1=0, ans2=1;if( bcc_cnt==1 ){ans1=2;ans2=bcc[1].size()*(bcc[1].size()-1)/2;} else {for ( int i=1; i<=bcc_cnt; i++ ){int cut_cnt=0;for ( int j=0; j<bcc[i].size(); j++ ) if( iscut[bcc[i][j]] ) cut_cnt++;if( cut_cnt==1 ) {ans1++;ans2*=(long long )(bcc[i].size()-cut_cnt); } }  }printf("Case %d: %lld %lld\n", ++kase, ans1, ans2); }return 0;
}