#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,pair<int,int> > > v;
int parent[10001];
int track(int x){ // find랑 같음
if(parent[x]==x){
return x;
}else{
int y = track(parent[x]);
parent[x]=y;
return y;
}
}
int main(){
int sum = 0;
int a,b,n1,n2,weight;
int tmp1,tmp2;
scanf("%d %d",&a,&b);
for(int i=0;i<=a;i++){
parent[i]=i;
}
// for(int i=0;i<=a;i++){
// printf("%d ",parent[i]);
// }
//벡터 저장하는 부분
for(int i=0;i<b;i++){
scanf("%d %d %d",&n1,&n2,&weight);
v.push_back(make_pair(weight/*가중치 젤 앞에 받음 (sort 알고리즘)*/,make_pair(n1,n2)));
}
sort(v.begin(),v.end()); // #include <algorithm> 해야 쓸 수 있음!
//유니온 파인드하는 부분
for(int i=0;i<b;i++){
tmp1 =v[i].second.first; //v[i] -> pair<int, pair<int,int> > 두번째 페어의 첫번째 거, ight는 그냥
tmp2 = v[i].second.second;
// printf("%d ",v[i].first);
tmp1 = track(tmp1); //최고조상찾기
tmp2 = track(tmp2); //...
if(tmp1==tmp2){ // 이미 연결됨
continue;
}else{ //연결이 안됨
sum+=v[i].first; // weight 꺼내서 더해줌
if(tmp1<tmp2){ //연결
parent[tmp2]=tmp1; //swap을 안함
}else{
parent[tmp1] = tmp2;
}
}
}
// for(int i=1;i<=a;i++){
// printf("%d ",parent[i]);
// }
// printf("\\n");
printf("%d",sum);
}
vector: 배열의 크기를 자유롭게 사용할 수 있음. 링크드 리스트로 구성!
pair<자료형, 자료형>
pair<int,int> : int 2개가 들어가는 구조체
vector<pair<int,pair<int,int> > > v;
pair<int,pair<int,int> >
pair<int,int>
이지선
이채연