模板-并查集DSU
版本1：路径压缩。
struct DSU {
std::vector<int> fa;
void init(int n) {
fa.resize(n + 1);
std::iota(fa.begin(), fa.end(), 0);
}
int leader(int x) {
while (x != fa[x]) {
fa[x] = leader(fa[x]);
}
return fa[x];
}
void join(int x, int y) {
x = leader(x);
y = leader(y);
if (x != y) {
fa[y] = x;
}
}
};
版本2：启发式合并。
struct DSU {
std::vector<int> fa, sz;
void init(int n) {
fa.resize(n + 1);
std::iota(fa.begin(), fa.end(), 0);
sz.assign(n + 1, 1);
}
int leader(int x) {
while (x != fa[x]) {
x = fa[x];
}
return x;
}
void join(int x, int y) {
x = leader(x);
y = leader(y);
if (x != y) {
if (sz[x] < sz[y]) {
std::swap(x, y);
}
sz[x] += sz[y];
fa[y] = x;
}
}
};
版本3：用map保存对应关系，适用于标识不是int的场景。
template<typename TYPE>
struct DSU {
std::map<TYPE,TYPE> fa;
std::map<TYPE,std::set<TYPE>> contain;
void add(TYPE x) {
fa[x] = x;
contain[x].insert(x);
}
void join(TYPE x, TYPE y) {
x = leader(x);
y = leader(y);
if (x != y) {
if (contain[x].size() < contain[y].size()) {
std::swap(x, y);
}
contain[x].insert(contain[y].begin(), contain[y].end());
fa[y] = x;
}
}
TYPE leader(TYPE x) {
return x == fa[x] ? x : fa[x] = get(fa[x]);
}
};