크루스칼 알고리즘은 최소한의 비용을 신장 트리를 찾을 때 사용하는 알고리즘입니다.

신장 트리?

신장트리는 하나의 그래프가 있을 떄 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다.

알고리즘 순서도

1. 간선 데이터를 비용에 따라 오름차순으로 정렬합니다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인합니다.
   1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다.
   2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않습니다.
3. 모든 간선에 대하여 2번의 과정을 반복합니다.

의사코드

#include <iostream>
#define Pair pair<int,pair<int,int>>
using namespace std;
int find_parent(vector<int> v,int x);
vector<int> union_parent(vector<int> v,int x,int y);
int main(void) {
  int n,m; cin >> n >> m;
  vector v(n+1,0);
  vector<Pair> edges;
  for (int i=1;i<=n;i++) {
    v[i]=i;
  }
  for (int i=0;i<m;i++) {
    int a,b,cost; cin >> a >> b >> cost;
    edges.push_back({cost,{a,b}});
  }
  int res = 0;
  sort(edges.begin(),edges.end());
  for (Pair edge: edges) {
    pair<int,int> cost = edge.second;
    if (find_parent(v,cost.first)!=find_parent(v,cost.second)) {
      v = union_parent(v,cost.first,cost.second);
      res+=edge.first;
    }
  }
  cout << res;
  return 0;
}
int find_parent(vector<int> v,int x) {
  if (v[x]!=x)v[x]=find_parent(v,v[x]);
  return v[x];
}
vector<int> union_parent(vector<int> v,int x,int y) {
  x = find_parent(v,x);
  y = find_parent(v,y);
  if (x<y) {
    v[y]=x;
  }else {
    v[x]=y;
  }
  return v;
}