15_mst.cpp

Download
cpp 334 lines 9.5 KB 
  1/*
  2 * ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ (Minimum Spanning Tree)
  3 * Kruskal, Prim, Union-Find
  4 *
  5 * ๊ทธ๋ž˜ํ”„์˜ ๋ชจ๋“  ์ •์ ์„ ์ตœ์†Œ ๋น„์šฉ์œผ๋กœ ์—ฐ๊ฒฐํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <queue>
 11#include <algorithm>
 12#include <numeric>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. Union-Find (Disjoint Set Union)
 18// =============================================================================
 19
 20class UnionFind {
 21private:
 22    vector<int> parent, rank_;
 23
 24public:
 25    UnionFind(int n) : parent(n), rank_(n, 0) {
 26        iota(parent.begin(), parent.end(), 0);
 27    }
 28
 29    int find(int x) {
 30        if (parent[x] != x) {
 31            parent[x] = find(parent[x]);  // ๊ฒฝ๋กœ ์••์ถ•
 32        }
 33        return parent[x];
 34    }
 35
 36    bool unite(int x, int y) {
 37        int px = find(x), py = find(y);
 38        if (px == py) return false;
 39
 40        // ๋žญํฌ ๊ธฐ๋ฐ˜ ํ•ฉ์น˜๊ธฐ
 41        if (rank_[px] < rank_[py]) swap(px, py);
 42        parent[py] = px;
 43        if (rank_[px] == rank_[py]) rank_[px]++;
 44
 45        return true;
 46    }
 47
 48    bool connected(int x, int y) {
 49        return find(x) == find(y);
 50    }
 51};
 52
 53// =============================================================================
 54// 2. Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜
 55// =============================================================================
 56
 57struct Edge {
 58    int u, v, weight;
 59    bool operator<(const Edge& other) const {
 60        return weight < other.weight;
 61    }
 62};
 63
 64pair<int, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
 65    sort(edges.begin(), edges.end());
 66
 67    UnionFind uf(n);
 68    vector<Edge> mst;
 69    int totalWeight = 0;
 70
 71    for (const auto& e : edges) {
 72        if (uf.unite(e.u, e.v)) {
 73            mst.push_back(e);
 74            totalWeight += e.weight;
 75
 76            if ((int)mst.size() == n - 1) break;
 77        }
 78    }
 79
 80    return {totalWeight, mst};
 81}
 82
 83// =============================================================================
 84// 3. Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜
 85// =============================================================================
 86
 87pair<int, vector<pair<int, int>>> prim(int n, const vector<vector<pair<int, int>>>& adj) {
 88    vector<bool> visited(n, false);
 89    vector<pair<int, int>> mst;  // {u, v} ๊ฐ„์„ 
 90    int totalWeight = 0;
 91
 92    // {weight, vertex, parent}
 93    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
 94    pq.push({0, 0, -1});
 95
 96    while (!pq.empty() && (int)mst.size() < n) {
 97        auto [w, u, parent] = pq.top();
 98        pq.pop();
 99
100        if (visited[u]) continue;
101        visited[u] = true;
102        totalWeight += w;
103
104        if (parent != -1) {
105            mst.push_back({parent, u});
106        }
107
108        for (auto [v, weight] : adj[u]) {
109            if (!visited[v]) {
110                pq.push({weight, v, u});
111            }
112        }
113    }
114
115    return {totalWeight, mst};
116}
117
118// =============================================================================
119// 4. 2์ฐจ ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ
120// =============================================================================
121
122int secondMST(int n, vector<Edge>& edges) {
123    // ๋จผ์ € MST ๊ตฌํ•˜๊ธฐ
124    auto [mstWeight, mst] = kruskal(n, edges);
125
126    int secondBest = INT_MAX;
127
128    // MST์˜ ๊ฐ ๊ฐ„์„ ์„ ์ œ๊ฑฐํ•˜๊ณ  ๋‹ค์‹œ MST ๊ตฌํ•˜๊ธฐ
129    for (int i = 0; i < (int)mst.size(); i++) {
130        vector<Edge> filtered;
131        for (const auto& e : edges) {
132            if (!(e.u == mst[i].u && e.v == mst[i].v && e.weight == mst[i].weight)) {
133                filtered.push_back(e);
134            }
135        }
136
137        auto [newWeight, newMst] = kruskal(n, filtered);
138
139        if ((int)newMst.size() == n - 1) {
140            secondBest = min(secondBest, newWeight);
141        }
142    }
143
144    return secondBest;
145}
146
147// =============================================================================
148// 5. ์ตœ๋Œ€ ์‹ ์žฅ ํŠธ๋ฆฌ
149// =============================================================================
150
151pair<int, vector<Edge>> maxSpanningTree(int n, vector<Edge>& edges) {
152    // ๊ฐ€์ค‘์น˜๋ฅผ ์Œ์ˆ˜๋กœ ๋ฐ”๊ฟ”์„œ Kruskal ์ ์šฉ
153    for (auto& e : edges) {
154        e.weight = -e.weight;
155    }
156
157    auto [weight, mst] = kruskal(n, edges);
158
159    // ์›๋ž˜ ๊ฐ€์ค‘์น˜๋กœ ๋ณต์›
160    for (auto& e : edges) {
161        e.weight = -e.weight;
162    }
163    for (auto& e : mst) {
164        e.weight = -e.weight;
165    }
166
167    return {-weight, mst};
168}
169
170// =============================================================================
171// 6. ํฌ๋Ÿฌ์Šค์ปฌ ์‘์šฉ: ์—ฐ๊ฒฐ ๋น„์šฉ ์ตœ์†Œํ™”
172// =============================================================================
173
174int minCostToConnect(int n, vector<vector<int>>& connections) {
175    vector<Edge> edges;
176    for (const auto& conn : connections) {
177        edges.push_back({conn[0] - 1, conn[1] - 1, conn[2]});
178    }
179
180    auto [cost, mst] = kruskal(n, edges);
181
182    if ((int)mst.size() != n - 1) {
183        return -1;  // ์—ฐ๊ฒฐ ๋ถˆ๊ฐ€
184    }
185
186    return cost;
187}
188
189// =============================================================================
190// 7. Union-Find ์‘์šฉ: ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ
191// =============================================================================
192
193class FriendNetwork {
194private:
195    unordered_map<string, string> parent;
196    unordered_map<string, int> size_;
197
198    string find(const string& x) {
199        if (parent.find(x) == parent.end()) {
200            parent[x] = x;
201            size_[x] = 1;
202        }
203        if (parent[x] != x) {
204            parent[x] = find(parent[x]);
205        }
206        return parent[x];
207    }
208
209public:
210    int unite(const string& a, const string& b) {
211        string pa = find(a), pb = find(b);
212
213        if (pa == pb) {
214            return size_[pa];
215        }
216
217        if (size_[pa] < size_[pb]) swap(pa, pb);
218        parent[pb] = pa;
219        size_[pa] += size_[pb];
220
221        return size_[pa];
222    }
223};
224
225// =============================================================================
226// 8. Union-Find ์‘์šฉ: ์ค‘๋ณต ์—ฐ๊ฒฐ ์ฐพ๊ธฐ
227// =============================================================================
228
229vector<int> findRedundantConnection(vector<vector<int>>& edges) {
230    int n = edges.size();
231    UnionFind uf(n + 1);
232
233    for (const auto& e : edges) {
234        if (!uf.unite(e[0], e[1])) {
235            return e;  // ์ค‘๋ณต ์—ฐ๊ฒฐ
236        }
237    }
238
239    return {};
240}
241
242// =============================================================================
243// ํ…Œ์ŠคํŠธ
244// =============================================================================
245
246int main() {
247    cout << "============================================================" << endl;
248    cout << "์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ์˜ˆ์ œ" << endl;
249    cout << "============================================================" << endl;
250
251    // ํ…Œ์ŠคํŠธ ๊ทธ๋ž˜ํ”„
252    //     1 --(4)-- 2
253    //    /|        /|
254    //  (1)|      (3)|
255    //  /  |      /  |
256    // 0   (2)   /   (5)
257    //  \  |  /      |
258    //  (3)| /       |
259    //    \|/        |
260    //     3 --(6)-- 4
261
262    int n = 5;
263    vector<Edge> edges = {
264        {0, 1, 1}, {0, 3, 3}, {1, 2, 4}, {1, 3, 2},
265        {2, 3, 3}, {2, 4, 5}, {3, 4, 6}
266    };
267
268    // 1. Kruskal
269    cout << "\n[1] Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜" << endl;
270    auto [kWeight, kMst] = kruskal(n, edges);
271    cout << "    MST ๊ฐ€์ค‘์น˜: " << kWeight << endl;
272    cout << "    MST ๊ฐ„์„ : ";
273    for (const auto& e : kMst) {
274        cout << "(" << e.u << "-" << e.v << ":" << e.weight << ") ";
275    }
276    cout << endl;
277
278    // 2. Prim
279    cout << "\n[2] Prim ์•Œ๊ณ ๋ฆฌ์ฆ˜" << endl;
280    vector<vector<pair<int, int>>> adj(n);
281    for (const auto& e : edges) {
282        adj[e.u].push_back({e.v, e.weight});
283        adj[e.v].push_back({e.u, e.weight});
284    }
285    auto [pWeight, pMst] = prim(n, adj);
286    cout << "    MST ๊ฐ€์ค‘์น˜: " << pWeight << endl;
287    cout << "    MST ๊ฐ„์„ : ";
288    for (const auto& [u, v] : pMst) {
289        cout << "(" << u << "-" << v << ") ";
290    }
291    cout << endl;
292
293    // 3. Union-Find
294    cout << "\n[3] Union-Find" << endl;
295    UnionFind uf(5);
296    uf.unite(0, 1);
297    uf.unite(2, 3);
298    uf.unite(1, 2);
299    cout << "    ํ•ฉ์นœ ํ›„: 0-1, 2-3, 1-2" << endl;
300    cout << "    0๊ณผ 3 ์—ฐ๊ฒฐ๋จ: " << (uf.connected(0, 3) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
301    cout << "    0๊ณผ 4 ์—ฐ๊ฒฐ๋จ: " << (uf.connected(0, 4) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
302
303    // 4. 2์ฐจ MST
304    cout << "\n[4] 2์ฐจ ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ" << endl;
305    vector<Edge> edges2 = edges;  // ๋ณต์‚ฌ
306    int secondWeight = secondMST(n, edges2);
307    cout << "    2์ฐจ MST ๊ฐ€์ค‘์น˜: " << secondWeight << endl;
308
309    // 5. ์ตœ๋Œ€ ์‹ ์žฅ ํŠธ๋ฆฌ
310    cout << "\n[5] ์ตœ๋Œ€ ์‹ ์žฅ ํŠธ๋ฆฌ" << endl;
311    vector<Edge> edges3 = edges;  // ๋ณต์‚ฌ
312    auto [maxWeight, maxMst] = maxSpanningTree(n, edges3);
313    cout << "    Max ST ๊ฐ€์ค‘์น˜: " << maxWeight << endl;
314
315    // 6. ์ค‘๋ณต ์—ฐ๊ฒฐ
316    cout << "\n[6] ์ค‘๋ณต ์—ฐ๊ฒฐ ์ฐพ๊ธฐ" << endl;
317    vector<vector<int>> redEdges = {{1, 2}, {1, 3}, {2, 3}};
318    auto redundant = findRedundantConnection(redEdges);
319    cout << "    ๊ฐ„์„ : (1,2), (1,3), (2,3)" << endl;
320    cout << "    ์ค‘๋ณต: (" << redundant[0] << ", " << redundant[1] << ")" << endl;
321
322    // 7. ๋ณต์žก๋„ ์š”์•ฝ
323    cout << "\n[7] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
324    cout << "    | ์•Œ๊ณ ๋ฆฌ์ฆ˜    | ์‹œ๊ฐ„๋ณต์žก๋„       | ํŠน์ง•              |" << endl;
325    cout << "    |-------------|------------------|-------------------|" << endl;
326    cout << "    | Kruskal     | O(E log E)       | ๊ฐ„์„  ๊ธฐ๋ฐ˜, ํฌ์†Œ   |" << endl;
327    cout << "    | Prim        | O((V+E) log V)   | ์ •์  ๊ธฐ๋ฐ˜, ๋ฐ€์ง‘   |" << endl;
328    cout << "    | Union-Find  | O(ฮฑ(n)) โ‰ˆ O(1)   | ๊ฑฐ์˜ ์ƒ์ˆ˜ ์‹œ๊ฐ„    |" << endl;
329
330    cout << "\n============================================================" << endl;
331
332    return 0;
333}