This documentation is automatically generated by online-judge-tools/verification-helper
#include "library/data-structure/dsu.hpp"
int n;
DSU d(n); // 只有路徑壓縮
DSU<true> d2(n); // 啟發式合併 + 路徑壓縮
int u, v;
int x = d.leader(u);
int sz = d.size(u);
bool success = d.merge(u, v);
bool is_same = d.same(u, v);
vector<vector<int>> g = d.groups();
#pragma once
#include <vector>
#include <cassert>
#include <algorithm>
namespace felix {
template<bool UNION_BY_SIZE = false>
struct dsu {
public:
dsu() : dsu(0) {}
explicit dsu(int _n) : n(_n), sz(n, -1) {}
int leader(int u) {
assert(0 <= u && u < n);
return (sz[u] < 0 ? u : (sz[u] = leader(sz[u])));
}
bool merge(int a, int b) {
a = leader(a), b = leader(b);
if(a == b) {
return false;
}
if constexpr(UNION_BY_SIZE) {
if(-sz[a] < -sz[b]) {
std::swap(a, b);
}
}
sz[a] += sz[b];
sz[b] = a;
return true;
}
int size(int u) { return -sz[leader(u)]; }
bool same(int a, int b) { return leader(a) == leader(b); }
std::vector<std::vector<int>> groups() {
std::vector<std::vector<int>> result(n);
for(int i = 0; i < n; i++) {
result[leader(i)].push_back(i);
}
result.erase(std::remove_if(result.begin(), result.end(), [](const std::vector<int>& v) {
return v.empty();
}), result.end());
return result;
}
private:
int n;
std::vector<int> sz;
};
} // namespace felix
#line 2 "library/data-structure/dsu.hpp"
#include <vector>
#include <cassert>
#include <algorithm>
namespace felix {
template<bool UNION_BY_SIZE = false>
struct dsu {
public:
dsu() : dsu(0) {}
explicit dsu(int _n) : n(_n), sz(n, -1) {}
int leader(int u) {
assert(0 <= u && u < n);
return (sz[u] < 0 ? u : (sz[u] = leader(sz[u])));
}
bool merge(int a, int b) {
a = leader(a), b = leader(b);
if(a == b) {
return false;
}
if constexpr(UNION_BY_SIZE) {
if(-sz[a] < -sz[b]) {
std::swap(a, b);
}
}
sz[a] += sz[b];
sz[b] = a;
return true;
}
int size(int u) { return -sz[leader(u)]; }
bool same(int a, int b) { return leader(a) == leader(b); }
std::vector<std::vector<int>> groups() {
std::vector<std::vector<int>> result(n);
for(int i = 0; i < n; i++) {
result[leader(i)].push_back(i);
}
result.erase(std::remove_if(result.begin(), result.end(), [](const std::vector<int>& v) {
return v.empty();
}), result.end());
return result;
}
private:
int n;
std::vector<int> sz;
};
} // namespace felix