标签：点双，tarjan
题目
Description
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
Input
输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
Output
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
Sample Input
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Sample Output
Case 1: 2 4
Case 2: 4 1
HINT
Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；
Case 2 的一组解为(4,5,6,7)。
分析
对于一个点双
-
如果它不和任何一个割点相连，那它就要建两个出口
-
如果它与一个相连，就见一个
-
如果与两个以上相连就不用建出口
方案就是每个点双去掉割点的点数之积
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e3+6;
struct edge{int to,next;}e[maxn<<1];
int n,m,T,low[maxn],dfn[maxn],top,que[maxn<<2],last[maxn],tim,cnt,cas,deg,tot,num,vis[maxn],ans1,root;
bool cut[maxn],inque[maxn];ll ans2;
void insert(int u,int v){
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void tarjan(int x){
dfn[x]=low[x]=++tim;que[++top]=x;inque[x]=1;
reg(x){
if(!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
else if(inque[e[i].to]){low[x]=min(low[x],dfn[e[i].to]);continue;}
if(dfn[x]<=low[e[i].to]){if(x==root)deg++;else cut[x]=1;}
}
}
void dfs(int x){
vis[x]=T;if(cut[x])return;tot++;
reg(x){
if(cut[e[i].to]&&vis[e[i].to]!=T)num++,vis[e[i].to]=T;
if(!vis[e[i].to])dfs(e[i].to);
}
}
int main()
{
while(1){
m=read();if(!m)break;
mem(e,0);mem(low,0);mem(dfn,0);mem(cut,0);mem(vis,0);mem(inque,0);mem(que,0);mem(last,0);
cnt=n=tim=T=ans1=top=0,cas++,ans2=1;
rep(i,1,m){
int x=read(),y=read();
insert(x,y);n=max(n,max(x,y));
}
rep(i,1,n){
if(!dfn[i]){tarjan(root=i);if(deg>=2)cut[root]=1;}
deg=0;
}
rep(i,1,n)
if(!vis[i]&&!cut[i]){
++T,tot=num=0,dfs(i);
if(!num)ans1+=2,ans2*=tot*(tot-1)/2;
if(num==1)ans1++,ans2*=tot;
}
printf("Case %d: %d %lld\n",cas,ans1,ans2);
}
return 0;
}
