01197번 최소 스패닝 트리

Problem link: https://www.acmicpc.net/problem/1197

Keywords: Minimum Spanning Tree, Kruskal Algorithm

정말 별 것이 없고 문제에 충실하게 MST를 잘 구해주면 된다.

Kruskal 또는 Prim을 쓰면 무리 없이 풀릴텐데, 이사 전 블로그에서 Prim을 쓰기도 했었고 disjoint set도 복습할 겸 여기서는 Kruskal로 풀었다.

아래는 솔루션이다.

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

using namespace std;

// Inputs.
int V;
int E;
struct Edge {
  int src;
  int dst;
  int weight;
  bool operator<(const Edge& rhs) const { return weight < rhs.weight; }
};
std::vector<Edge> EDGES;

// Solution.
std::vector<int> PARENT;

int Find(int n) {
  if (PARENT[n] == -1) {
    return n;
  } else {
    return (PARENT[n] = Find(PARENT[n]));
  }
}

void Union(int a, int b) { PARENT[Find(a)] = Find(b); }

int64_t Solve() {
  PARENT.assign(V + 1, -1);
  sort(EDGES.begin(), EDGES.end());

  int64_t cost = 0;
  for (const auto& edge : EDGES) {
    if (Find(edge.src) != Find(edge.dst)) {
      Union(edge.src, edge.dst);
      cost += edge.weight;
    }
  }

  return cost;
}

int main(void) {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  // Read inputs.
  cin >> V >> E;
  EDGES.resize(E);
  for (int i = 0; i < E; ++i) {
    cin >> EDGES[i].src >> EDGES[i].dst >> EDGES[i].weight;
  }

  // Solve.
  cout << Solve() << "\n";

  return 0;
}