Test/DataStructure/DisjointSetUnion.test.cpp

• View this file on GitHub
• Last update: 2024-12-25 00:03:38+09:00
• Problem: https://yukicoder.me/problems/no/1390

Depends on

• Library/DataStructure/DisjointSetUnion.hpp

Code

#include <vector>

#define PROBLEM "https://yukicoder.me/problems/no/1390"

#include <iostream>


// begin:tag includes

#include "./../../Library/DataStructure/DisjointSetUnion.hpp"

// end:tag includes


signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int>> cv(n);
  for (int _ = 0; _ < n; ++_) {
    int b, c;
    std::cin >> b >> c;
    cv[c - 1].emplace_back(b - 1);
  }

  auto dsu = mtd::PotentialDisjointSetUnion(m);

  int ans = 0;
  for (const auto& v : cv)
    if (!v.empty()) {
      auto base = v.front();
      for (const auto& tg : v) {
        if (!dsu.isSame(base, tg)) {
          dsu.unite(base, tg);
          ++ans;
        }
      }
    }
  std::cout << ans << std::endl;
}

#line 1 "Test/DataStructure/DisjointSetUnion.test.cpp"
#include <vector>

#define PROBLEM "https://yukicoder.me/problems/no/1390"

#include <iostream>


// begin:tag includes

#line 2 "Library/DataStructure/DisjointSetUnion.hpp"

#line 4 "Library/DataStructure/DisjointSetUnion.hpp"
#include <numeric>

#line 6 "Library/DataStructure/DisjointSetUnion.hpp"

namespace mtd {

  template <class T = int>
  class PotentialDisjointSetUnion {
    std::vector<int> m_root;
    std::vector<int> m_rank;
    std::vector<int> m_size;
    std::vector<T> m_potential;

  public:
    PotentialDisjointSetUnion() = delete;
    PotentialDisjointSetUnion(int n)
        : m_root(n), m_rank(n), m_size(n, 1), m_potential(n) {
      std::iota(m_root.begin(), m_root.end(), 0);
    }

    auto unite(int x, int y, T p = 0) {
      p += potential(x);
      p -= potential(y);
      x = root(x);
      y = root(y);
      if (x == y) { return false; }
      if (m_rank[x] < m_rank[y]) {
        std::swap(x, y);
        p = -p;
      }
      if (m_rank[x] == m_rank[y]) { ++m_rank[x]; }
      m_size[x] = m_size[y] = size(x) + size(y);
      m_root[y] = x;
      m_potential[y] = p;
      return true;
    }

    auto root(int x) -> int {
      if (m_root[x] == x) { return x; }
      int r = root(m_root[x]);
      m_potential[x] += m_potential[m_root[x]];
      return m_root[x] = r;
    }

    auto potential(int x) -> T {
      root(x);
      return m_potential[x];
    }

    auto size(int x) -> int {
      if (m_root[x] == x) { return m_size[x]; }
      return size(m_root[x] = root(m_root[x]));
    }

    auto isSame(int x, int y) { return root(x) == root(y); }

    auto diff(int x, int y) { return potential(y) - potential(x); }

    friend std::ostream& operator<<(std::ostream& os,
                                    const PotentialDisjointSetUnion& dsu) {
      for (const auto& x : dsu.m_root) { os << x << " "; }
      return os;
    }
  };
}  // namespace mtd

#line 8 "Test/DataStructure/DisjointSetUnion.test.cpp"
// end:tag includes


signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int>> cv(n);
  for (int _ = 0; _ < n; ++_) {
    int b, c;
    std::cin >> b >> c;
    cv[c - 1].emplace_back(b - 1);
  }

  auto dsu = mtd::PotentialDisjointSetUnion(m);

  int ans = 0;
  for (const auto& v : cv)
    if (!v.empty()) {
      auto base = v.front();
      for (const auto& tg : v) {
        if (!dsu.isSame(base, tg)) {
          dsu.unite(base, tg);
          ++ans;
        }
      }
    }
  std::cout << ans << std::endl;
}

Back to top page