[BOJ] 1647번 도시 분할 계획

문제 바로가기

접근

#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int a;
  int b;
  int c;

  Edge(int a, int b, int c): a(a), b(b), c(c) {}
};

struct compare {
  bool operator() (Edge const& a, Edge const& b) {
    return a.c > b.c;
  }
};

priority_queue<Edge, vector<Edge>, compare> pq;
vector<int> parent;

int find(int x) {
  if(parent[x] == x)
    return x;
  return parent[x] = find(parent[x]);
}

void merge(int a, int b) {
  a = find(a);
  b = find(b);

  if(a != b)
    parent[b] = a;
}

bool isCyclic(int n1, int n2) {
  if(find(n1) == find(n2))
    return true;
  merge(n1, n2);
  return false;
}

int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int N, M, A, B, C;
  int cost = 0, cnt = 0;

  cin >> N >> M;
  for(int i = 0; i < N + 1; i++)
    parent.push_back(i);
  for(int i = 0; i < M; i++) {
    cin >> A >> B >> C;
    pq.push(Edge(A, B, C));
  }

  while(!pq.empty()) {
    if(cnt == N - 2)
      break;

    Edge e = pq.top();
    pq.pop();

    if(!isCyclic(e.a, e.b)) {
      cnt++;
      cost += e.c;
    }
  }

  cout << cost;
}