矿场搭建

题目描述：

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

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

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

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

思路：

对于一个没有割点的一个整个的连通块，至少存在两个出口，才能使的该连通块内的任意一个点都能跑到出口去

一个割点会至少连接两个连通分量，所以对于只含一个割点的连通分量，它内部只需要一个出口即可

对于含两个及以上割点的连通分量，它里面就不需要设置出口

原因是，对于一个连通块，根据割点进行缩点后，形成一棵树，每个节点都是一个个小的连通分量，每个连通分量的割点的数量就是树上该节点的度，存在两个及以上的割点也就是度不为1，即非叶子节点，因为我们给度数为1的连通分量都放了一个出口，也就叶子节点都有出口，而度数不为1的节点必然存在两条能到达不同叶子的路径，所以是该叶子节点中不需要放出口

我们可以根据上面的讨论方式，求出若干个连通块的放置出口的方法，各个连通块之间互不影响，所以乘起来就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tmd;
int dfn[MAX], low[MAX];
stack<int>st;
int dcc_cnt;
vector<int>dcc[MAX];
bool ge[MAX];
void tarjan(int u, int root){
    st.push(u);
    dfn[u] = low[u] = ++tmd;
    
    if(u == root && !head[u]){//特判掉孤立点
        dcc[++dcc_cnt].push_back(u);
        return;
    }
    int child = 0;//记录分支数量，即孩子的数量
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v, root);
            low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v]){
                ++child;//只有下面的点无法跑出u的时候，才说明它是孩子节点
                if(root != u || child > 1)ge[u] = 1;//目的是判掉不存在割点的单独的连通块
                ++dcc_cnt;//更新连通分量的数量
                int now;
                do {
                    now = st.top();st.pop();
                    dcc[dcc_cnt].push_back(now);
                } while (now != v);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
    
}

void init(){
    n = 0;
    tot = 0;
    mem(head, 0);
    
    tmd = 0;
    mem(dfn, 0);
    mem(low, 0);
    
    while (!st.empty()) st.pop();
    for(int i = 1; i <= dcc_cnt; ++i)dcc[i].clear();
    dcc_cnt = 0;
    
    mem(ge, 0);
}


void work(){
    int t = 0;
    while (cin >> m && m) {
        for(int a, b, i = 1; i <= m; ++i){
            cin >> a >> b;
            n = max({n, a, b});
            add(a, b);add(b, a);
        }
        for(int i = 1; i <= n; ++i){
            if(!dfn[i])tarjan(i, i);
        }
        ull res = 0, ans = 1;
        for(int i = 1; i <= dcc_cnt; ++i){
            int num = 0;
            for(auto x : dcc[i]){
                if(ge[x])++num;
            }
            if(num == 0){
                if(dcc[i].size() == 1)++res;
                else {
                    res += 2;
                    ans *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                }
            }
            else if(num == 1){
                ++res;
                ans *= dcc[i].size() - 1;
            }
        }
        printf("Case %d: %llu %llu\n",++t,res,ans);
        init();
    }
}


int main(){
    io;
    work();
    return 0;
}