38 lines
850 B
C++
38 lines
850 B
C++
#pragma once
|
|
#include <vector>
|
|
#include <utility>
|
|
|
|
struct DSU {
|
|
std::vector<int> dsu_parent;
|
|
std::vector<int> dsu_rank;
|
|
|
|
DSU() {}
|
|
explicit DSU(int n) { init(n); }
|
|
|
|
void init(int n) {
|
|
dsu_parent.resize(n + 1);
|
|
dsu_rank.assign(n + 1, 0);
|
|
for (int i = 0; i <= n; ++i) dsu_parent[i] = i;
|
|
}
|
|
|
|
int find(int x) {
|
|
while (dsu_parent[x] != x) {
|
|
dsu_parent[x] = dsu_parent[dsu_parent[x]];
|
|
x = dsu_parent[x];
|
|
}
|
|
return x;
|
|
}
|
|
|
|
bool unite(int a, int b) {
|
|
a = find(a);
|
|
b = find(b);
|
|
if (a == b) return false;
|
|
if (dsu_rank[a] < dsu_rank[b]) std::swap(a, b);
|
|
dsu_parent[b] = a;
|
|
if (dsu_rank[a] == dsu_rank[b]) ++dsu_rank[a];
|
|
return true;
|
|
}
|
|
|
|
bool same(int a, int b) { return find(a) == find(b); }
|
|
};
|