Untitled
unknown
plain_text
2 years ago
1.6 kB
6
Indexable
#include <iostream> #include <algorithm> #include <vector> using namespace std; struct Edge { int u, v, w; }; struct DSU { vector<int> parent, rank; DSU(int n) { parent.resize(n + 1); rank.resize(n + 1); for (int i = 1; i <= n; i++) { parent[i] = i; rank[i] = 1; } } int find(int u) { if (parent[u] == u) { return u; } return parent[u] = find(parent[u]); } void merge(int u, int v) { u = find(u); v = find(v); if (u == v) { return; } if (rank[u] > rank[v]) { swap(u, v); } parent[u] = v; rank[v] += rank[u]; } }; bool cmp(Edge e1, Edge e2) { return e1.w < e2.w; } pair<vector<Edge>, int> kruskal(int n, vector<Edge> edges) { sort(edges.begin(), edges.end(), cmp); vector<Edge> result; DSU dsu(n); int cost = 0; for (auto e : edges) { if (dsu.find(e.u) != dsu.find(e.v)) { dsu.merge(e.u, e.v); result.push_back(e); cost += e.w; } if (result.size() == n - 1) { break; } } return make_pair(result, cost); } int main() { int n, m; cout << "Introduceti numarul de noduri: "; cin >> n; cout << "Introduceti numarul de muchii: "; cin >> m; vector<Edge> edges(m); cout << "Introduceti muchiile sub forma u v w:\n"; for (int i = 0; i < m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } auto result = kruskal(n, edges); cout << "Arborele de cost minim este:\n"; for (auto e : result.first) { cout << e.u << " " << e.v << " " << e.w << "\n"; } cout << "Costul total al arborelui de cost minim este: " << result.second << "\n"; return 0; } //noduri 5 muchii7 //1 2 2 //1 4 2 //1 5 3 //2 3 5 //2 5 5 //3 4 4 //4 5 2
Editor is loading...