Union-Find
(datastructure/union-find-tree.hpp)

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Include: #include "datastructure/union-find-tree.hpp"

Required by

• 最小全域木 (クラスカル法) (graph/mst-kruskal.hpp)

Verified with

• test/aoj/DSL_1_A.test.cpp
• test/aoj/GRL_2_A.test.cpp

Code

/**
 * @title Union-Find
 */
#include <vector>

class UnionFind {
public:
  std::vector<int> data; // sizeとparを同時に管理する
  UnionFind(int size) : data(size, -1) {}
  int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
  void unite(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
      if (data[py] < data[px]) std::swap(px, py);
      data[px] += data[py]; data[py] = px;
    }
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -data[find(x)]; }
};

#line 1 "datastructure/union-find-tree.hpp"
/**
 * @title Union-Find
 */
#include <vector>

class UnionFind {
public:
  std::vector<int> data; // sizeとparを同時に管理する
  UnionFind(int size) : data(size, -1) {}
  int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
  void unite(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
      if (data[py] < data[px]) std::swap(px, py);
      data[px] += data[py]; data[py] = px;
    }
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -data[find(x)]; }
};

Back to top page