# 題目: UVa 10972 - RevolC FaeLoN

# 題目說明

Koorosh現在是一名高級顧問，他在沒有你的幫助下解決了Basm的問題
跟往常一樣，Basm征服了一個新地區，叫做RevolC FaeLoN
為了讓RevolC FaeLoN的人民滿意，他想要使該國的道路變成單向來降低事故發生率
他希望每個城市都有一條路能到其他城市，所以他要求Koorosh找到需要建造的最少道路數

---

INPUT:
每筆測資的第一行有兩個整數n及m，n代表城市的數量，m代表道路的數量
接下來會有m行，每行有兩個整數u及v，代表u、v城市間有一條道路連接

---

OUTPUT:
輸出需要建造道路的最小數量

# 解題方法

無相圖中的邊雙聯通分量，定向後一定為強連通分量

先找出每個BCC(Bridge Connected Component)的bridge數量

• 對於2個以上bridge的BCC，必定有進來及離開這些城市的路
• 對於1個bridge的BCC，總共需要(x + 1) / 2條道路才能全部連接 (x為1個bridge的BCC的數量)
• 對於0個bridge的BCC，總共需要y條道路才能全部連接 (y為0個bridge的BCC的數量)
  所以總共需要(x + 1) / 2 + y條道路

# 參考程式碼

• 0個bridge的BCC，用vector<int> bridge找出
• 1個bridge的BCC，用每個點的low值找出

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector< vector<int> > G;
vector<int> dfn, low, bridge;
int dep;

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

    for (auto& v : G[u])
    {
        if (!dfn[v])
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if (v != par) low[u] = min(low[u], low[v]);     

        if (low[v] > low[u]) bridge.emplace_back(v), bridge.emplace_back(u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, a, b;
    while (cin >> n >> m)
    {
        // init
        G.assign(n + 1, vector<int>());
        dfn.assign(n + 1, 0);
        low.assign(n + 1, 0);
        bridge.clear();
        dep = 0;
        int con1 = 0, con0 = 0;

        // store data
        while (m--)
        {
            cin >> a >> b;
            G[a].emplace_back(b);
            G[b].emplace_back(a);
        }

        // find bridge connected component
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
            {
                size_t s = bridge.size();
                dfs(i, -1);
                if (s == bridge.size()) ++con0;
            }

        // solve
        if (bridge.size() == 0 && con0 == 1) cout << "0\n";
        else
        {
            map<int, int> m;
            for (int i = 1; i <= n; ++i) 
            {           
                m[low[i]] += 0;
                for (auto& v : G[i]) if (low[v] != low[i]) ++m[low[i]];
            }

            for (auto& [__, de] : m) if (de == 1) ++con1;

            cout << con0 + (con1 + 1) / 2 << "\n";           
        }        
    }

    return 0;
}

# 參考文章:

https://www.larrysprognotes.com/UVa%20-%2010972/