# Untitled

unknown
plain_text
a year ago
1.6 kB
1
Indexable
Never
```#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```