题目描述
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
输入
输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
输出
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
样例输入
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
样例输出
Case 1: 2 4
Case 2: 4 1
题解
可也看出如果塌在割点才有影响
所以先跑出所以割点，然后删去割点跑联通块
如果一个块有两个割点那么无所谓。
否则建一个方案为点数
最后如果只要一个联通块，那么就要两个点。方案数为n*（n-1）/2
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge
{
int END, next;
} v[10005];
int first[500], p;
void add(int a, int b)
{
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
int dfn[500], low[500], Index;
bool iscut[500];
void Tarjan(int x, int fa)
{
low[x] = dfn[x] = ++Index;
int S = 0;
for (int i = first[x]; i != -1; i = v[i].next)
{
if (!dfn[v[i].END])
{
S++;
Tarjan(v[i].END, x);
low[x] = min(low[v[i].END], low[x]);
if (low[v[i].END] >= dfn[x])
iscut[x] = 1;
}
else
low[x] = min(low[x], dfn[v[i].END]);
}
if (fa < 0 && S == 1)
iscut[x] = 0;
}
bool vis[500];
int T, size, num;
int color[500];
void dfs(int x)
{
vis[x] = 1;
size++;
for (int i = first[x]; i != -1; i = v[i].next)
{
if (!vis[v[i].END])
{
if (!iscut[v[i].END])
dfs(v[i].END);
else
{
if (color[v[i].END] != T)
color[v[i].END] = T, num++;
}
}
}
}
int main()
{
//freopen("bzoj_2730.in","r",stdin);
//freopen("bzoj_2730.out","w",stdout);
int P1 = 0;
while (1)
{
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(iscut, 0, sizeof(iscut));
memset(first, -1, sizeof(first));
memset(color, 0, sizeof(color));
p = 0;
Index = 0;
P1++;
int n = 0, a, b, m;
scanf("%d", &m);
if (m == 0)
break;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a, &b);
n = max(a, n);
n = max(b, n);
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
Tarjan(i, -1);
int ans1 = 0;
long long ans2 = 1;
T = 0;
for (int i = 1; i <= n; i++)
{
if (!vis[i] && !iscut[i])
{
T++, size = 0, num = 0;
dfs(i);
if (num == 1)
ans1++, ans2 *= size;
}
}
if (T == 1)
ans1 = 2, ans2 = n * (n - 1) / 2;
printf("Case %d: %d %lld\n", P1, ans1, ans2);
}
}