看到删去一个点，需要剩下的都和关键点连通，有端联想到找点双，因为他怎么删点都是连通的。
对于一个孤立的点双，至少要设两个关键点。
如果两个点双以一个割点连接，假设断掉这个割点，两个块至少要各设一个关键点。类推，所以对于所有含有一个割点的点双，至少要包含非割点的一个关键点。
如果一个点双上有好多个割点，可以不设点，因为把图看成缩掉点双的一棵树，有一个割点的点双一定在叶子处，有多个割点的点双因为有许多树枝，删掉一个，一定可以仍与某一方的叶子（也就是位于叶子处的点双中的关键点）连通，所以不要设。
这样，讨论完毕，统计方案也就很好搞了。
注意一点：孤立点要特判，因为他只要设一个点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef unsigned long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=+;
map<int,int> mp;
struct thxorz{int to,nxt;}G[N];
int Head[N],tot;
int n,m,ans,T;
ll typ;
inline void Addedge(int x,int y){
G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot;
G[++tot].to=x,G[tot].nxt=Head[y],Head[y]=tot;
}
#define y G[j].to
vector<int> dcc[N];
int dfn[N],low[N],stk[N],cut[N],cnt,rt,Top,dcnt;
void tarjan(int x){
dfn[x]=low[x]=++cnt;int chd=;
if(x==rt&&!Head[x]){dcc[++dcnt].push_back(x);return;}
stk[++Top]=x;
for(register int j=Head[x];j;j=G[j].nxt){
if(!dfn[y]){
++chd;tarjan(y);MIN(low[x],low[y]);//forget MIN...
if(low[y]==dfn[x]){//or low[y]>=dfn[x]
if(x==rt&&chd>=||x^rt)cut[x]=;
int tmp;++dcnt;
do tmp=stk[Top--],dcc[dcnt].push_back(tmp);while(tmp^y);
dcc[dcnt].push_back(x);
}
}
else MIN(low[x],dfn[y]);
}
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
while(read(m),m){
mp.clear();n=ans=;typ=;
memset(Head,,sizeof Head);tot=;
for(register int i=,x,y;i<=m;++i){
read(x),read(y);
if(mp.find(x)==mp.end())mp[x]=++n;
if(mp.find(y)==mp.end())mp[y]=++n;
Addedge(mp[x],mp[y]);
}
memset(dfn,,sizeof dfn),memset(low,,sizeof low),memset(cut,,sizeof cut);dcnt=cnt=;
for(register int i=;i<=n;++i)if(!dfn[i])Top=,rt=i,tarjan(i);
for(register int i=,tt=,siz;i<=dcnt;++i,tt=){
for(register int j=;j<dcc[i].size();++j)if(cut[dcc[i][j]])++tt;
siz=dcc[i].size();
if(siz==)++ans;
else if(!tt)ans+=,typ*=siz*(siz-)/;
else if(tt==)++ans,typ*=(siz-);
dcc[i].clear();
}
printf("Case %d: %d %llu\n",++T,ans,typ);
}
return ;
}
智障WA：line42的MIN漏写了。。果然tarjan还是不熟练啊。
总结：遇到删点和连通性联系在一起的问题时多往点双上想一想，当然凡是点双都要考虑比较特殊的情况，如：2个点，以及孤立点。