# 題目: UVA 1108 - Mining Your Own Business

# 題目說明

John Digger是一座礦坑的擁有者，礦坑是由大量的地道及連接點組成
不像某些人，Digger關心礦工的安全，他擔心礦坑會崩塌，於是他打算設置安全通道
但是他又不想在每個連接點都設置安全通道，他希望能設置最低數量的安全通道，當礦坑崩塌時，所有礦工都能藉由地道到安全通道

---

INPUT:
每筆測資的第一行為一個整數N，代表地道的數量
接下來會有N行，每行有兩個整數s與t，代表這兩個連接點透過地道相連
當N為0時結束

---

OUTPUT:
先輸出第幾個case，接著輸出最少的安全通道數量及此數量的情況數

# 解題方法

此題為點雙連通分量的應用題

點這裡詳細解釋點雙連通分量，及此題的另一種參考解法

---

先找到每個連通圖的割點數量

• 對於兩個割點以上的連通圖，即使一個割點崩塌，仍可以透過另一個割點到安全通道。
• 如果只有一個割點，那連通圖中至少要有一個安全通道
• 如果沒有割點的連通圖，那至少要設置兩個安全通道，當一個安全通道崩塌時，還可以到達另一個安全通道

總方法數的求法為只有一個割點的連通圖的方法數相乘
沒有割點的連通圖的方法數則為C(N)取2

# 參考程式碼

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

vector< vector<int> > G;
vector< unordered_set<int> > bcc;
vector<int> dfn, low;
vector<bool> iscut;
stack< pair<int, int> > S;
int dep;

void dfs(int u, int par)
{
    int child = 0;
    dfn[u] = low[u] = ++dep;

    for (auto& v : G[u]) 
    {
        if (!dfn[v]) 
        {
            ++child;
            S.push({ u, v });

            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u]) 
            {
                iscut[u] = true;
                unordered_set<int> US;
                while(1)
                {
                    int cu = S.top().first, cv = S.top().second; S.pop();                 
                    US.emplace(cu), US.emplace(cv);
                    if (cu == u && cv == v) break;
                }
                bcc.emplace_back(US);
            }         
        }
        else if (dfn[v] < dfn[u] && v != par) low[u] = min(low[u], dfn[v]);
    }

    if (par == -1 && child == 1) iscut[u] = false;
}

int main()
{
    // fast io
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N, cases = 0;
    while (cin >> N, N) 
    {
        // init
        G.assign(N + 2, vector<int>()), bcc.clear();
        dfn.assign(N + 2, 0), low.assign(N + 2, 0);
        iscut.assign(N + 2, false);
        dep = 0;

        // store data
        for (int i = 0, a, b; i < N; ++i) 
        {
            cin >> a >> b;
            G[a].emplace_back(b);
            G[b].emplace_back(a);
        }

        // find bcc and bcc's element
        dfs(1, -1);

        // solve
        long long ans1 = 0, ans2 = 1;
        if (bcc.size() == 1) ans1 = 2, ans2 = bcc[0].size() * (bcc[0].size() - 1) / 2;
        else for (auto& i : bcc)
        {
            int count = 0;
            for (auto& j : i) if (iscut[j]) ++count;
            if (count == 1) ++ans1, ans2 *= i.size() - 1;
        }

        cout << "Case " << ++cases << ": " << ans1 << " " << ans2 << "\n";
    }

    return 0;
}

# 參考文章:

https://reurl.cc/e8lZmm
https://reurl.cc/Q3AG5q

---