[BOJ] 1197번 최소 스패닝 트리

문제 바로가기

접근

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

struct Edge {
  int x;
  int y;
  int w;

  Edge(int x, int y, int w): x(x), y(y), w(w) {}
};

struct compare {
  bool operator() (Edge const& e1, Edge const& e2) {
    return e1.w > e2.w;
  }
};

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 x, int y) {
  x = find(x);
  y = find(y);

  if(x != y)
    parent[y] = x;
}

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 V, E;
  int x, y, w, cost = 0;

  cin >> V >> E;
  for(int i = 0; i < V + 1; i++)
    parent.push_back(i);
  for(int i = 0; i < E; i++) {
    cin >> x >> y >> w;
    pq.push(Edge(x, y, w));
  }

  while(!pq.empty()) {
    Edge e = pq.top();
    pq.pop();

    if(!isCyclic(e.x, e.y))
      cost += e.w;
  }

  cout << cost;
}