Notes

// Minimum Spanning Tree Algorithm (MST), Kruskal

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

#define MAXN 500
#define pb push_back

using namespace std;

typedef pair<int,int> ii;

struct edge{

int a,b,len;

friend bool operator < ( const edge &first , const edge &second ){
return first.len < second.len;
}
};

int N,M;
int rep[MAXN]; // rep[i] i numalari nodeun o an bulundugu unionuin temsilcisi

vector<edge> E;

int find( int nd ){ // nd numarali nodeun bulundugu uniounun temsilcisini bulan fonksiyon

if( nd == rep[nd] ) // Temsilciyi bulduk
return nd;

return rep[nd] = find(rep[nd]); // Bu node temsilci degilse bir sonraki adima geciyoruz, daha sonraki sorgularda isimizi kolaylastirmasi icin de rep[nd] yerine gelen sonucu yaziyoruz
}

int main(){

scanf("%d%d",&N,&M); // N tane node, M tane edge var

for( int a,b,c,i=0 ; i<M ; i++ ){

scanf("%d%d%d",&a,&b,&c);

edge k;
k.a = a;
k.b = b;
k.len = c;

E.pb(k); // Bu kez graphi liste ya a matris seklinde tutmuyoruz. Sadece edgelerin listesini tutuyoruz, Kruskal algorithmasi icin edgelerin kucukten buyuge siralanmis hali yeterli
}

for( int i=1 ; i<=N ; i++ ) // MST'yi olusturmadan once her node kendi basina bir union
rep[i] = i;

sort(E.begin(),E.end()); // Edgeleri kucukten buyuge sıralıyoruz

int i=0;
int cnt = 0;
int sum = 0;

while( cnt<N-1 ){ // N-1 tane edgei agaca ekledikten sonra baska edge eklemeye calismanin bir anlami yok

int a = E[i].a; // Siradaki edgein bagladigi nodelar a ve b
int b = E[i].b;
int len = E[i].len; // Edgein agirligi(uzunluk, maliyet, deger vs. problem neyse artik)

if( find(a) != find(b) ){ // a ve b nodelari ayni unionda degillerse bu edgei agaca ekleyebiliriz, uzunluk kontrolu yapmiyoruz cunku daha sonra ele alacagimiz edgelrin hic biri bu edgeden daha kucuk degil
rep[find(a)] = find(b); // Iki uniondan birinin temsilcisini digerine baglamak yeterli
cnt++; // Bir edge ekledigimiz icin cnt++
sum += len; // Toplam maliyetimiz edgedin agirligi kadar artti
}

i++; // Sonraki edge e gectik
}

printf("%dn",sum);
return 0;
}