抄题解真开心
我真是越来越菜了
这是点双的板子题，于是求出所有点双，之后讨论
如果点双里之有一个割点，那么如果这个割点炸了，这个点双就出不去了，于是我们得在这个点双内部除了这个割点位置放一个
如果有两个割点，那么无论哪个割点炸了，这个点双都还有其他出口，于是不用放
没有割点，那么可能就是一个孤立的环，我们肯定得放一个在里面，但是如果放的位置炸了，这个环还是不和外部联通，于是只能再放一个以备不测
之后第二问用乘法原理就可以啦
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<vector>
#define re register
#define maxn 505
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
struct E
{
int u,v,nxt;
}e[maxn<<1];
int head[maxn];
int n,num,m;
std::vector<int> bcc[maxn];
std::stack<int> st;
int col[maxn],tot,cnt;
int dfn[maxn],low[maxn];
inline void add_edge(int x,int y)
{
e[++num].u=x,e[num].v=y;
e[num].nxt=head[x],head[x]=num;
}
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
int now;
int cut[maxn];
void tarjan(int x,int fa)
{
int sz=0;
dfn[x]=low[x]=++cnt;
for(re int i=head[x];i;i=e[i].nxt)
if(!dfn[e[i].v])
{
sz++;
st.push(i);
tarjan(e[i].v,x);
if(low[e[i].v]<low[x]) low[x]=low[e[i].v];
if(low[e[i].v]>=dfn[x])
{
cut[x]=1;
bcc[++tot].clear();
for(;;)
{
int k=st.top();
st.pop();
if(col[e[k].u]!=tot) bcc[tot].push_back(e[k].u),col[e[k].u]=tot;
if(col[e[k].v]!=tot) bcc[tot].push_back(e[k].v),col[e[k].v]=tot;
if(i==k) break;
}
}
}else if(fa!=e[i].v&&dfn[e[i].v]<low[x]) low[x]=dfn[e[i].v],st.push(i);
if(!fa&&sz<2) cut[x]=0;
}
inline int init()
{
now++;
m=read(),n=0;
if(!m) return 0;
int x,y;
memset(head,0,sizeof(head));
num=0;
for(re int i=1;i<=m;i++)
x=read(),y=read(),add_edge(x,y),add_edge(y,x),n=max(n,max(x,y));
memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low));
cnt=0,tot=0;
memset(col,0,sizeof(col)),memset(cut,0,sizeof(cut));
for(re int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,0);
int ans=0;
long long total=1;
for(re int i=1;i<=tot;i++)
{
int t=0,k=0;
for(std::vector<int>::iterator j=bcc[i].begin();j!=bcc[i].end();++j)
{
t++;
if(cut[*j]) k++;
}
if(k==1) ans++,total*=(long long)(t-1);
if(!k) total*=(long long)(t-1)*t/2,ans+=2;
}
printf("Case %d: %d %lld",now,ans,total),putchar(10);
return m;
}
int main()
{
while(init());
return 0;
}