[BOJ] 1922번 네트워크 연결

문제 바로가기

접근

#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 a) {
  if(parent[a] == a)
    return a;
  return parent[a] = find(parent[a]); // 경로 압축
  // find(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;
  int cost = 0;
  int a, b, c;

  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()) {
    Edge e = pq.top();
    pq.pop();

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

  cout << cost;
}