struct DSU {
vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
使用示例:
DSU dsu(n+1);DSU fn(n+1);
int r1=dsu.find(u),r2=dsu.find(v);
fn.merge(u,v);
标签:不带权,return,dsu,int,siz,查集,jly,DSU,find
From: https://www.cnblogs.com/mathiter/p/17873772.html