This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
経路圧縮とサイズ比較をどちらも行っているため、クエリあたりの計算量は $O(\alpha(N))$ になっているはず。
find(x)
: $x$ が属する集合の代表元を返すsame(x, y)
: $x$ と $y$ が同じ集合に属するかどうかの bool 値を返すsize(x)
: $x$ が属する集合の濃度 (要素数) を返すsize()
: 素集合がいくつ存在するかを返すunite(x, y)
: $x$ と $y$ が同じ集合に属するなら false
を返す。そうでなければ true
を返すとともに、$x$ が属する集合と $y$ が属する集合を併合する#pragma once
/**
* @brief Union-Find
* @docs docs/structure/union_find.md
*/
#include <algorithm>
#include <vector>
struct UnionFind {
private:
const int n;
int size_;
vector<int> uf;
public:
// 初期化 UnionFind uni(n) のように宣言すれば良い
UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
void reset() {
size_ = n;
fill(uf.begin(), uf.end(), -1);
}
// find (木の根を求める)
int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
// x と y が同じ集合に属するかどうか
bool same(int x, int y) {return find(x) == find(y);}
// x が属する集合の要素数
int size(int x) {return -uf[find(x)];}
// 集合はいくつあるか
int size() {return size_;}
// x と y の属する集合を併合
bool unite(int x, int y) {
x = find(x); y = find(y);
if(x == y) return false;
size_--;
if(-uf[x] < -uf[y]) swap(x, y);
uf[x] += uf[y]; uf[y] = x;
return true;
}
};
#line 2 "structure/union_find.cpp"
/**
* @brief Union-Find
* @docs docs/structure/union_find.md
*/
#include <algorithm>
#include <vector>
struct UnionFind {
private:
const int n;
int size_;
vector<int> uf;
public:
// 初期化 UnionFind uni(n) のように宣言すれば良い
UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
void reset() {
size_ = n;
fill(uf.begin(), uf.end(), -1);
}
// find (木の根を求める)
int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
// x と y が同じ集合に属するかどうか
bool same(int x, int y) {return find(x) == find(y);}
// x が属する集合の要素数
int size(int x) {return -uf[find(x)];}
// 集合はいくつあるか
int size() {return size_;}
// x と y の属する集合を併合
bool unite(int x, int y) {
x = find(x); y = find(y);
if(x == y) return false;
size_--;
if(-uf[x] < -uf[y]) swap(x, y);
uf[x] += uf[y]; uf[y] = x;
return true;
}
};