This documentation is automatically generated by online-judge-tools/verification-helper
#include "data_structure/dsu.hpp"
$2$ つのグループを同じグループにする、 $2$ つの要素が同じグループか判定、が可能なデータ構造。ここで、 $\alpha(N)$ をアッカーマン関数の逆関数とする。
$N$ 要素のdsuを構築する。 $O(N)$
$x$ と $y$ が同じグループか判定。 $O(\alpha(N))$
$x$ のグループと $y$ のグループをマージ。 $O(\alpha(N))$
$x$ のグループの代表を返す。 $O(\alpha(N))$
$x$ のグループのサイズを返す。 $O(\alpha(N))$
グループの個数を求める。 $O(n)$
初期状態にする。 $O(N)$
#pragma once
#include <algorithm>
#include <vector>
namespace ebi {
struct dsu {
private:
std::vector<int> par;
int c;
public:
dsu(int n = 0) : par(n, -1), c(n) {}
bool same(int x, int y) {
return leader(x) == leader(y);
}
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
if (par[x] > par[y]) std::swap(x, y);
par[x] += par[y];
par[y] = x;
c--;
return true;
}
int leader(int x) {
if (par[x] < 0)
return x;
else
return par[x] = leader(par[x]);
}
int size(int x) {
return -par[leader(x)];
}
int count_group() const {
return c;
}
std::vector<std::vector<int>> groups() {
int n = par.size();
std::vector result(n, std::vector<int>());
for (int i = 0; i < n; i++) {
result[leader(i)].emplace_back(i);
}
result.erase(std::remove_if(result.begin(), result.end(),
[](const std::vector<int> &v) -> bool {
return v.empty();
}),
result.end());
return result;
}
void clear() {
for (int i = 0; i < int(par.size()); i++) {
par[i] = -1;
}
}
};
} // namespace ebi
#line 2 "data_structure/dsu.hpp"
#include <algorithm>
#include <vector>
namespace ebi {
struct dsu {
private:
std::vector<int> par;
int c;
public:
dsu(int n = 0) : par(n, -1), c(n) {}
bool same(int x, int y) {
return leader(x) == leader(y);
}
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
if (par[x] > par[y]) std::swap(x, y);
par[x] += par[y];
par[y] = x;
c--;
return true;
}
int leader(int x) {
if (par[x] < 0)
return x;
else
return par[x] = leader(par[x]);
}
int size(int x) {
return -par[leader(x)];
}
int count_group() const {
return c;
}
std::vector<std::vector<int>> groups() {
int n = par.size();
std::vector result(n, std::vector<int>());
for (int i = 0; i < n; i++) {
result[leader(i)].emplace_back(i);
}
result.erase(std::remove_if(result.begin(), result.end(),
[](const std::vector<int> &v) -> bool {
return v.empty();
}),
result.end());
return result;
}
void clear() {
for (int i = 0; i < int(par.size()); i++) {
par[i] = -1;
}
}
};
} // namespace ebi