BOJ1922_네트워크 연결(크루스칼, C++)

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

using namespace std;

struct Edge {
  int cost;
  int a;
  int b;
};

bool cmp (Edge a, Edge b) {
  if(a.cost >= b.cost) return false;
  else return true;
}


int N, M;
int parent[1001];
vector<Edge> edges;
int result;

int getParent(int a) {
  if (parent[a] == a) return a;
  return parent[a] = getParent(parent[a]);
}

void unionParent(int a, int b) {
  a = getParent(a);
  b = getParent(b);
  if(a < b) parent[b] = a;
  else parent[a] = b;
}

int main (void) {
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  cin >> N >> M;

  for(int i = 1; i <= N; i++) {
    parent[i] = i;
  }

  for(int i = 0; i < M; i++) {
      int a, b, cost;
      cin >> a >> b >> cost;
      edges.push_back({cost, a, b});
  }

  sort(edges.begin(), edges.end(), cmp);

  for(int i = 0; i < edges.size(); i++) {
    int cost = edges[i].cost;
    int a = edges[i].a;
    int b = edges[i].b;

    if(getParent(a) != getParent(b)) {
      unionParent(a, b);
      result += cost;
    }
  }

  cout << result << endl;
}