BOJ 7044 - Bad Cowtractors

BOJ 7044 - Bad Cowtractors

단순 MST 문제이다.

struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m;
   cin >> n >> m;
   vector<array<int, 3>> edges;
   DSU dsu(n);
   while (m--) {
      int a, b, c;
      cin >> a >> b >> c, a--, b--;
      edges.pb({c, a, b});
   }
   sort(all(edges), greater<>());
   int ans = 0;
   for (auto &[c, a, b]: edges) {
      if (!dsu.is_merged(a, b)) {
         ans += c;
         dsu.merge(a, b);
      }
   }
   if (dsu.size(0) != n) cout << -1;
   else cout << ans;
}