# 題目: UVa 11747 - Heavy Cycle Edges

# 題目說明

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

---

INPUT:
每筆測資第一行有兩個整數n和m

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

接下來有m行，每行有三個整數u、v、w
代表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/