test/unionfind.test.cpp

• View this file on GitHub
• Last update: 2025-11-07 09:14:02+08:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Union-Find (Disjoint Set Union) Data Structure (weilycoder/ds/unionfind.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include "../weilycoder/ds/unionfind.hpp"
#include <iostream>
using namespace std;
using namespace weilycoder;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  size_t n, q;
  cin >> n >> q;
  UnionFind uf(n);
  for (size_t _ = 0; _ < q; ++_) {
    size_t op, x, y;
    cin >> op >> x >> y;
    switch (op) {
    case 0:
      uf.unite(x, y);
      break;
    case 1:
      cout << (uf.getf(x) == uf.getf(y) ? "1\n" : "0\n");
      break;
    }
  }
  return 0;
}

#line 1 "test/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#line 1 "weilycoder/ds/unionfind.hpp"



/**
 * @file unionfind.hpp
 * @brief Union-Find (Disjoint Set Union) Data Structure
 */

#include <algorithm>
#include <numeric>
#include <vector>

namespace weilycoder {
/**
 * @brief Union-Find (Disjoint Set Union) Data Structure
 * @tparam ptr_t Type for representing indices (default: size_t)
 */
template <typename ptr_t = size_t> struct UnionFind {
private:
  std::vector<ptr_t> parent, setSize;

public:
  /**
   * @brief Constructs a UnionFind with n elements, each in its own set
   * @param n Number of elements
   */
  UnionFind(ptr_t n) : parent(n), setSize(n, 1) {
    std::iota(parent.begin(), parent.end(), 0);
  }

  /**
   * @brief Returns the number of elements
   * @return Number of elements
   */
  size_t size() const { return parent.size(); }

  /**
   * @brief Returns the size of the set containing x
   * @param x Element to query
   * @return Size of the set containing x
   */
  size_t get_size(ptr_t x) { return setSize[getf(x)]; }

  /**
   * @brief Finds the representative of the set containing x
   * @param x Element to find
   * @return Representative of the set containing x
   */
  ptr_t getf(ptr_t x) {
    while (x != parent[x])
      x = parent[x] = parent[parent[x]];
    return x;
  }

  /**
   * @brief Unites the sets containing x and y
   * @param x First element
   * @param y Second element
   * @return True if the sets were separate and have been united, false if they
   *         were already in the same set
   */
  bool unite(ptr_t x, ptr_t y) {
    x = getf(x), y = getf(y);
    if (x == y)
      return false;
    if (setSize[x] < setSize[y])
      std::swap(x, y);
    parent[y] = x, setSize[x] += setSize[y];
    return true;
  }
};
} // namespace weilycoder


#line 4 "test/unionfind.test.cpp"
#include <iostream>
using namespace std;
using namespace weilycoder;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  size_t n, q;
  cin >> n >> q;
  UnionFind uf(n);
  for (size_t _ = 0; _ < q; ++_) {
    size_t op, x, y;
    cin >> op >> x >> y;
    switch (op) {
    case 0:
      uf.unite(x, y);
      break;
    case 1:
      cout << (uf.getf(x) == uf.getf(y) ? "1\n" : "0\n");
      break;
    }
  }
  return 0;
}

Back to top page