Untitled

#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