# 題目: UVa 11747 - Heavy Cycle Edges

# 題目說明

給一個無向圖,其中有數個點及邊
連通使一點能走到任意點 (以最小的 weight)
求多餘的邊的 weight (會造成 circle 的邊的 weight)


INPUT:
每筆測資第一行有兩個整數 nm

  1. n 代表點的數量
  2. m 代表邊的數量

接下來有 m 行,每行有三個整數 uvw
代表 u 點及 v 點間有一條 weight 為 w 的邊


OUTPUT:
輸出會造成 circle 的邊的 weight
如果沒有則輸出 forest

# 解題方法

先將所有點的編號及 weight 存入 edge
接著以 kruskcal 演算法,先對 weight 進行 sort ,再用 union_find 演算法判斷是否可連通
將不能連通的邊依序輸出

# 參考程式碼

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
vector< tuple<int, int, int> > edge;
vector<int> parents;
vector<int> ranks;
bool cmp(tuple<int, int, int> s1, tuple<int, int, int> s2)
{
    return get<2>(s1) < get<2>(s2);
}
bool union_find(int u, int v)
{
    // find root of u and v
    while (u != parents[u]) u = parents[u];
    while (v != parents[v]) v = parents[v];
    // circle
    if (u == v) return false;
    if (ranks[u] > ranks[v]) parents[v] = u;
    else if (ranks[v] > ranks[u]) parents[u] = v;
    else parents[v] = u, ++ranks[u];
    return true;
}
void kruskcal()
{
    sort(edge.begin(), edge.end(), cmp);
    bool forest = true;
    for (auto& [u, v, w] : edge) if (!union_find(u, v))
    {
        if (!forest) cout << " ";
        cout << w;
        forest = false;
    }
    if (forest) cout << "forest";
    cout << "\n";
}
int main()
{
    // fast io
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n && m)
    {
        // init
        edge.clear();
        parents.clear();
        ranks.assign(n, 0);
        for (int i = 0; i < n; ++i) parents.emplace_back(i);
        // store side and weight
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            edge.push_back({ u, v, w });
        }
        
        // kruskcal algorithm
        kruskcal();
    }
    return 0;
}

# 參考資料

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