朴素并查集
// 每个点的父亲节点
int p[N];
// 每个集合的大小
int sz[N];
void init(int n) {
for (int i = 1;
i <= n;
i ++ ) {
p[i] = i;
sz[i] = 1;
}
}int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}void merge(int x, int y) {
x = find(x), y = find(y);
p[x] = y;
sz[y] += sz[x];
}【并查集】带路径压缩的并查集
// 每个点的父亲节点
int p[N];
// 每个点距离根节点的距离
int dist[N];
// 每个集合的大小
int sz[N];
void init(int n) {
for (int i = 1;
i <= n;
i ++ ) {
p[i] = i;
dist[i] = 0;
sz[i] = 1;
}
}int find(int x) {
if (p[x] == x) return x;
int root = find(p[x]);
d[x] += d[p[x]];
return p[x] = root;
}void merge(int x, int y) {
x = find(x), y = find(y);
p[x] = y;
d[x] = sz[y];
sz[y] += sz[x];
}
