MST.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long

bool compare(vector<int> &a, vector<int>&b){
	return a[2] < b[2];
}

int findParent(int u, vector<int>&parent){
	if(parent[u]==u){
		return u;
	}
	return parent[u] = findParent(parent[u],parent);
}

void Union(int u, int v, vector<int>&rank, vector<int>&parent){
	int parU = findParent(u,parent);
	int parV = findParent(v,parent);
	if(parU == parV){
		return ;
	}
	if(rank[parU] > rank[parV]){
		parent[parV] = parent[parU];
	}
	else if(rank[parU] < rank[parV]){
		parent[parU] = parent[parV];
	}
	else{
		parent[parU] = parent[parV];
		rank[parV]++;
	}
}

int main(){

	int nodes;
	cin>>nodes;
	int edgesCount;
	cin>>edgesCount;
	vector<vector<int>>graph(nodes);
	vector<vector<int>>edges;
	for(int i=0;i<edgesCount;i++){
		int sou,des,wt;
		cin>>sou>>des>>wt;
		edges.push_back({sou,des,wt});
		graph[sou].push_back(des);
		graph[des].push_back(sou);
	}

	vector<int>parent(nodes);
	vector<int>rank(nodes,0);
	for(int i=0;i<nodes;i++){
		parent[i]=i;
	}
	sort(edges.begin(),edges.end(), compare);
	int cost = 0;
	for(int i=0;i<edges.size();i++){
		int sou = edges[i][0];
		int des = edges[i][1];
		if(parent[sou]!=parent[des]){
			cost+=edges[i][2];
			Union(sou,des,rank,parent);
		}
	}
	cout<<cost;

	return 0;
}