题目：Mining Your Own Business
思路：tarjan求双连通分量。对于每个双连通分量，如果只包含一个割点，则需要在不是割点的任意地方放两个太平井。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 100000
#define ll long longstruct E {int x,y;E(int xx=0,int yy=0) {x=xx,y=yy;}
};int n,m;vector<int> a[maxn+5];int pre[maxn+5],low[maxn+5];
int clk;vector<int> bcc[maxn+5];
int cnt;bool iscut[maxn+5];stack<E> s;int sum[maxn+5];void readin() { //读入 n=0;map<int,int> id;for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);if(!id.count(x)) id[x]=++n;if(!id.count(y)) id[y]=++n;a[x].push_back(y),a[y].push_back(x);}
}void init() { //初始化 for(int i=0; i<=maxn; i++) a[i].clear();memset(pre,0,sizeof(pre));memset(low,0,sizeof(low));memset(iscut,0,sizeof(iscut));cnt=clk=0;
}void tj(int u,int fa) { //tarjanpre[u]=low[u]=++clk;int chld=0;for(int i=0; i<a[u].size(); i++) {int v=a[u][i];if(v==fa) continue;if(!pre[v]) {s.push(E(u,v));chld++;tj(v,u);low[u]=min(low[u],low[v]);if(low[v]>=pre[u]) {iscut[u]=true;cnt++;bcc[cnt].clear();set<int> h;E x;do {x=s.top(),s.pop();if(h.find(x.x)==h.end()) {bcc[cnt].push_back(x.x);h.insert(x.x);}if(h.find(x.y)==h.end()) {bcc[cnt].push_back(x.y);h.insert(x.y);}} while(!(u==x.x&&v==x.y));}} else if(pre[v]<pre[u]) {s.push(E(u,v));low[u]=min(low[u],pre[v]); //注意不是low[v] }}if(fa<0&&chld==1) iscut[u]=false; //注意特判
}void print(int& T) { //输出 printf("Case %d: ",++T);if(cnt==1) printf("2 %lld\n",n*((ll)n-1)/2); //注意特判 else {ll ans=0,k=1;for(int i=1; i<=cnt; i++) {sum[i]=0;for(int j=0; j<bcc[i].size(); j++) {if(iscut[bcc[i][j]]) sum[i]++;}if(sum[i]==1) {ans++;k*=(bcc[i].size()-1);}}printf("%lld %lld\n",ans,k);}
}int main() {int T=0;while(~scanf("%d",&m)&&m) {init();readin();tj(1,-1);print(T);}return 0;
}