博客题解：https://www.cnblogs.com/Tyouchie/p/10426016.html

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式
输入文件有若干组数据，每组数据的第一行是一个正整数 N，表示工地的隧道数。

接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖煤点 S 与挖煤点 T 由隧道直接连接。

输入数据以 0 结尾。

输出格式
每组数据输出结果占一行。

其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 264，输出格式参照以下输入输出样例。

数据范围
1≤N≤500
输入样例：
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

思路

首先我们知道，对于这张图，我们可以枚举坍塌的是哪个点，对于每个坍塌的点，最多可以将图分成若干个不连通的块，这样每个块我们可能需要一个出口才能满足题目的要求，枚举每个坍塌的点显然是没有意义的，我们只需要每个图的若干个割点，这样除去割点的图有若干个块，我们可以求出只与一个割点相连的块，这些块必须要一个出口才能满足题目的要求，每个块内有块内个数种选法，然后将所有满足一个割点相连的块的点数连乘就行了。

对于每个与一个割点相连的块必须建出口可以换一种方式理解，我们将每个块看做一个点，那么算上割点之后，这张图就变成了一颗树，只有叶子节点我们需要建立出口，因为对于非叶子节点我们不论断掉哪个点我们都有另一种方式相连，这里的叶子节点就是与一个割点相连的块。
最后还有个特判，就是对于一个双连通图，我们至少需要选取两个点作为出口，因为如果就选一个，可能该点为坍塌点，这时我们就任选两个点就行了，方案数为点数x(点数-1)>>1。

代码该如何写？
先tarjan求一下所有的点双。
然后对于每一个点双，分类讨论：
1、只有一个割点，必须选一个非割点。
2、有>=2个割点，不用选
3、有0个割点，必须选俩。
画个图理解一下撒；

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
struct gg {
    int y,next;
}a[maxn*maxn];
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    if (ch=='-') f=-1, ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
long long hl,ans=1;
int lin[maxn],len;
inline void add(int x,int y) {
    a[++len].y=y;
    a[len].next=lin[x];
    lin[x]=len;
}
int dfn[maxn],low[maxn],num,root;
bool cut[maxn];
inline void tarjan(int x,int fa) {
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(!dfn[y]) {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]) {
                ++flag;
                if (x!=root||flag>1) cut[x]=1;
            }
        }
        else if (y!=fa)
            low[x]=min(low[x],dfn[y]);
    }
}
int vis[maxn],k,cnt;
inline void dfs(int x){
    vis[x]=k;
    ++cnt;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(vis[y]!=k&&cut[y]) ++num,vis[y]=k;
        if(!vis[y]) dfs(y);
    }
}
int main() {
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    for(int ca=1;;++ca) {
        int n=0,m;
        read(m);
        if(!m) exit(0);
        memset(dfn,0,sizeof(dfn));
        memset(vis,0,sizeof(vis));
        memset(cut,0,sizeof(cut));
        memset(lin,0,sizeof(lin));
        hl=k=num=len=0;
        ans=1;
        for(int i=1;i<=m;++i) {
            int x,y;read(x);read(y);
            n=max(n,max(x,y));
            add(x,y);add(y,x);
        }
        for(int i=1;i<=n;++i)
            if(!dfn[i]) root=i,tarjan(i,i);
        for(int i=1;i<=n;++i)
            if(!vis[i]&&!cut[i])
            {
                ++k,cnt=num=0;
                dfs(i);
                if(!num) hl+=2,ans*=cnt*(cnt-1)/2;
                if(num==1) hl++,ans*=cnt;
            }
        printf("Case %d: %lld %lld\n",ca,hl,ans);
    }
    return 0;
}