78. 원더랜드 (Kruskal MST 알고리즘)

▣ 입력설명
첫째 줄에 도시의 개수 V(1≤V≤25)와 도로의 개수 E(1≤E≤200가 주어진다. 다음 E개의 줄에
는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시
가 유지비용이 C인 도로로 연결되어 있다는 의미이다. C는 값이 1,000,000을 넘지 않는다.
▣ 출력설명
모든 도시를 연결하면서 드는 최소비용을 출려한다.
▣ 입력예제 1
[C++를 이용한 창의적 문제 해결]

• 84 -
  9 12
  1 2 12
  1 9 25
  2 3 10
  2 8 17
  2 9 8
  3 4 18
  3 7 55
  4 5 44
  5 6 60
  5 7 38
  7 8 35
  8 9 15
  ▣ 출력예제 1
  196

#include
#include
#include
#include
using namespace std;
int unf[1001];
struct Edge{
int s;
int e;
int val;
Edge(int a,int b, int c){
s=a;
e=b;
val=c;
}
bool operator<(const Edge &b) const {
return val<b.val; // 가중치 값으로 정렬하기 내림차순으로
}
};

int Find(int v){
if(v==unf[v]) return v;
else return unf[v]=Find(unf[v]);
}

void Union(int a,int b){
a=Find(a);
b=Find(b);
if(a!=b)unf[a]=b;
}
int main() {

vector<Edge> Ed; //Edge라는 구조체 형성 
int i,n,m,a,b,c,cnt=0,res=0;
cin>>n>>m; // 노드 갯수 , 간선 수
for(i=1;i<=n;i++){
	unf[i]=i;
	
} 

for(i=1;i<=m;i++){
	cin>>a>>b>>c;
	Ed.push_back(Edge(a,b,c)); //구조체에 값 넣기 
}
sort(Ed.begin(),Ed.end()); // 정렬하기 
for(i=0;i<m;i++){
	int fa=Find(Ed[i].s);
	int fb=Find(Ed[i].e);
	if(fa!=fb){
		res+=Ed[i].val;
		Union(Ed[i].s,Ed[i].e);
	}
} 
cout<<res;

}