題目： UVa - 11747 - Heavy Cycle Edges

題目說明

給一個無向圖，使得所有點連通，並且優先選擇權重較小的邊，求多餘的邊。

Input： 每組測資的第一行為兩個整數 n、m，分別代表點的數量及邊的數量，若兩者皆為 0 則結束。後面 m 行，每行有三個整數 u、v、w，表示有邊 (u, v)，權重為 w。

Output： 輸出所有多餘的邊的權重，若沒有多餘的邊則輸出 "forest"。

解題思路

這個解法需要有 Union Find 及 Kruskcal 演算法的概念。

使用 Union Find 及 Kruskcal 找出最小生成樹，所有不在樹裡面的邊即是多餘的邊，邊做邊輸出即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// reference: https://ppt.cc/f0psNx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct edge
{
    int u;
    int v;
    int w;

    // 根據權重排序
    bool operator<(const edge& r) { return w < r.w; }
};

// data
int n, m; // input
vector<edge> edges;
int parents[1001]; // 每個點的 parent
int ranks[1001];

void init()
{
    edges.clear();
    // 一開始每個節點的 parent 都是自己，而 rank 皆為 0
    for (int i = 0; i < n; ++i) parents[i] = i, ranks[i] = 0;
}

int Find(int p) { return p == parents[p] ? p : parents[p] = Find(parents[p]); }

bool Union(int x, int y)
{
    int rx = Find(x), ry = Find(y);

    // 如果 x 跟 y 的 root 一樣，表示 x 和 y 接起會造成環
    if (rx == ry) return false;

    // 將 rank 較小的接到 rank 較大的樹下面，因為這樣後面 Find 時消耗較小
    if (ranks[x] > ranks[y]) parents[ry] = rx;
    else if (ranks[x] < ranks[y]) parents[rx] = ry;
    else parents[ry] = rx, ++ranks[rx];

    return true;
}

void kruskcal()
{
    bool isOut = false; // 是否已經有輸出

    for (auto& [u, v, w] : edges)
    {
        if (Union(u, v)) continue;

        // 若 u、v 已經連通了表示邊 (u, v) 是多餘的邊
        if (isOut) cout << ' ';
        cout << w;
        isOut = true;
    }

    if (!isOut) cout << "forest";
    cout << '\n';
}

int main()
{
    while (cin >> n >> m && !(!n && !m))
    {
        init();

        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            edges.push_back({ u, v, w });
        }

        sort(edges.begin(), edges.end());

        kruskcal();
    }
}

參考資料

[UVA] 11747 - Heavy Cycle Edges @ 程式碼備份區 :: 痞客邦 ::