首先我们知道，对于这张图，我们可以枚举坍塌的是哪个点，对于每个坍塌的点，最多可以将图分成若干个不连通的块，这样每个块我们可能需要一个出口才能满足题目的要求，枚举每个坍塌的点显然是没有意义的，我们只需要每个图的若干个割点，这样除去割点的图有若干个块，我们可以求出只与一个割点相连的块，这些块必须要一个出口才能满足题目的要求，每个块内有块内个数种选法，然后将所有满足一个割点相连的块的点数连乘就行了。
对于每个与一个割点相连的块必须建出口可以换一种方式理解，我们将每个块看做一个点，那么算上割点之后，这张图就变成了一颗树，只有叶子节点我们需要建立出口，因为对于非叶子节点我们不论断掉哪个点我们都有另一种方式相连，这里的叶子节点就是与一个割点相连的块。
最后还有个特判，就是对于一个双连通图，我们至少需要选取两个点作为出口，因为如果就选一个，可能该点为坍塌点，这时我们就任选两个点就行了，方案数为点数*(点数-1)>>1。
/**************************************************************
Problem: 2730
User: SLL
Language: C++
Result: Accepted
Time:40 ms
Memory:2952 kb
****************************************************************/
//By BLADEVIL
#include
#include
#define maxn 50000
using namespace std;
int n;
int last[maxn],pre[maxn],other[maxn];
int dfn[maxn],low[maxn],cut[maxn],vis[maxn],size[maxn],num[maxn],flag[maxn],fuck[maxn];
int l,time;
long long ans1,ans2,task;
void getmin(int &x,int y)
{if (yy;}
void connect(int x,int y)
{
pre[++l]=last[x];
last[x]=l;
other[l]=y;
}
void dfs(int x,int fa)
{
low[x]=dfn[x]=++time;
int q,p,cnt=0;
for (q=last[x];q;q=pre[q])
{
p=other[q];
if (p==fa) continue;
if (!dfn[p])
{
dfs(p,x); cnt++;
getmin(low[x],low[p]);
if (dfn[x]<=low[p]&&fa!=-1) cut[x]=1;
} else getmin(low[x],dfn[p]);
}
if (fa==-1&&cnt>1) cut[x]=1;
}
void make(int x,int fa)
{
int p;
for (int q=last[x];q;q=pre[q])
{
p=other[q];
if (p==fa||cut[p]) continue;
if (!vis[p]) vis[p]=vis[x],make(p,x);
}
}
void solve()
{
int m=n; n=0;
while (m--)
{
int x,y;
scanf("%d%d",&x,&y);
connect(x,y); connect(y,x);
n=(x>n)?x:n;
n=(y>n)?y:n;
fuck[x]=fuck[y]=1;
}
for (int i=1;i<=n;i++) if (!dfn[i]) dfs(i,-1);
//for (int i=1;i<=n;i++) if (cut[i]) printf("%d ",i);
for (int i=1;i<=n;i++) if (!(vis[i]||cut[i])) vis[i]=i,make(i,-1);
//for (int i=1;i<=n;i++) printf("%d ",vis[i]); printf("\n");
for (int i=1;i<=n;i++) if (vis[i]) size[vis[i]]++;
for (int i=1;i<=n;i++)
if (cut[i])
{
memset(flag,0,sizeof flag);
for (int q=last[i];q;q=pre[q])
if (!flag[vis[other[q]]]) flag[vis[other[q]]]=1,num[vis[other[q]]]++;
}
//for (int i=1;i<=n;i++) printf("%d %d %d\n",i,size[i],num[i]);
for (int i=1;i<=n;i++)
if (num[i]==1) ans1++,ans2*=size[i];
if (!ans1)
{
ans2=0;
for (int i=1;i<=n;i++)
if (fuck[i]) ans2++;
}
if (!ans1)
printf("Case %lld: %lld %lld\n",task,2ll,ans2*(ans2-1)>>1); else
printf("Case %lld: %lld %lld\n",task,ans1,ans2);
}
void clear()
{
time=l=ans1=0ll; ans2=1ll;
memset(last,0,sizeof last);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(cut,0,sizeof cut);
memset(vis,0,sizeof vis);
memset(size,0,sizeof size);
memset(num,0,sizeof num);
memset(fuck,0,sizeof fuck);
}
int main()
{
scanf("%d",&n);
while (n)
{
task++;
clear();
solve();
scanf("%d",&n);
}
return 0;
}
京公网安备 11010802041100号