396. 矿场搭建

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

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

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

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

输入格式

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

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

注意，每组数据的挖煤点的编号为 1∼Max，其中 Max 表示由隧道连接的挖煤点中，编号最大的挖煤点的编号，可能存在没有被隧道连接的挖煤点。

输入数据以 0 结尾。

输出格式

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

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

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

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

数据范围

1≤N≤500，
1≤Max≤1000

输入样例：

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

思路：

/* 给一个不一定连通的无向图 问最少在几个点设置出口 使得任意一个出口坏掉后,其他所有点都可以和某些出口连通 首先考虑 1 出口数量>=2 如果只有一个出口 那这个出口坏了就没有可以用的出口了（孤点单独判断） 2 不同连通块之间相互独立(最终方案数 = 各连通块方案数乘积) 对一个连通块 2.1 无割点 <=> 不管我删掉哪个点 图剩余部分都是连通的、且剩余好出口>=1 <=> 度数==0 <=> 孤立的点 那么我们必须设置2个出口就可以满足 连通块中点个数=cnt 方案数=C[cnt][2] = cnt*(cnt-1)/2 2.2 有割点 <=> 点双连通分量 缩点(每个割点都属于2个点双连通分量) 2.2.1 先将所有割点单独出来作为一个点 2.2.2 从每个点双连通分量(V-DCC)向其所包含的每个割点连一条边 o o / \ / \ o---.---.---o \ / o 缩完点后 .-割点 o-连通块 o-.-o-.-o 同时缩完后的o中包含之前有连的 2.2.3 看V-DCC度数 2.2.3.1 如果V-DCC==1 意味着它只包含一个割点(上图中左和右) 则如果这个割点是出口且坏掉 这个V-DCC就无法连到其他出口了 所以V-DCC==1 时 必须在V-DCC内(非割点)放置一个出口 2.2.3.2 如果V-DCC>1 就不需要设置出口 证明: 1 如果割点坏了 缩完点后,此时所有度数==1的点相当于一个叶子节点-所有度数为1的叶子节点放一个出口 因此每个叶子节点必然会有一个出口 .(割点) ×/ \× o o(连通块) 2 如果度数为1的右边的V-DCC里的某个点坏了 由于是V-DCC 删去坏点后仍然是一个V-DCC .(割点) / \ o @(连通块中坏了一个点) 但此时不影响这个V-DCC到割点 并通过割点到左边V-DCC中的出口 3 如果度数为2的V-DCC里的某个点坏了 由于度数==2 <=> 必然连接两个割点 o(连通块) / \ . .(割点) 每个割点必然有一个出口 所以可以从上面的o到下面的两个割点到其他V-DCC找到出口 总结: 1 无割点 放2个出口 方案数 *= C[cnt][2] = cnt*(cnt-1)/2 2 有割点 V-DCC==1 放1个出口 方案数 *= C[cnt-1][1] = cnt-1 (不包含割点) 3 有割点 V-DCC>=2 放0个出口 方案数 *= 1 */

代码：

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N]; // 不能id 因为重复点属于不同点连通分量
bool cut[N];

void add(int a, int b)
{
    
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void tarjan(int u, int root)
{
    
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;

    if (u == root && h[u] == -1) // 特判孤点
    {
    
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
    
        int j = e[i];
        if (!dfn[j])
        {
    
            tarjan(j, root);
            low[u] = min(low[u], low[j]);
            if (dfn[u] <= low[j]) // 判断分支
            {
    
                cnt++;
                if (u != root || cnt > 1) //判断割点
                    cut[u] = true;

                /* 本质放入栈中的是边，（按访问顺序）一个边只属于一个点的双连通分量，而一个割点属于多个点的双连通分量， 如果入栈的是点，弹出来后这个点只能给一个点的双连通分量。 */
                dcc_cnt++;
                int y;
                do
                {
    
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);          // 所以u不弹出来
                dcc[dcc_cnt].push_back(u); // 加上u
            }
        }
        else
            low[u] = min(low[u], dfn[j]);
    }
}

int main()
{
    
    int T = 1;
    while (cin >> m, m)
    {
    
        for (int i = 1; i <= dcc_cnt; i++)
            dcc[i].clear();
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(cut, 0, sizeof cut);

        while (m--)
        {
    
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
            n = max(n, a), n = max(n, b);
        }

        for (int i = 1; i <= n; i++)
        {
    
            if (!dfn[i])
                tarjan(i, i);
        }
        int res = 0;
        ULL num = 1;

        for (int i = 1; i <= dcc_cnt; i++)
        {
    
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j++) //统计每个连通块中的割点 即缩点后的度数
            {
    
                if (cut[dcc[i][j]])
                    cnt++;
            }

            if (cnt == 0)
            {
    
                if (dcc[i].size() > 1) // 大于两个点的图至少两个出口
                    res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                else // 特判
                    res++;
            }
            else if (cnt == 1) // 一个割点 则点连通分量除了割点之外 其他点中选一个
                res++, num *= dcc[i].size() - 1;
            //大于2 不变化
        }
        printf("Case %d: %d %llu\n", T++, res, num);
    }

    return 0;
}