网上抄的
constexpr int N = 1e7 + 10;
struct lset {
int p[N], rank[N], sz; //p[N]:根节点，rank[N]:根节点展开的树的深度
void link(int x, int y) {
if (x == y)
return;
if (rank[x] > rank[y]) //x深度大于y，则y链到x下。
p[y] = x;
else
p[x] = y;
if (rank[x] == rank[y]) //如果深度相同且根节点不同，则新的根节点的深度+1
rank[y]++;
}
void init(int n) { //初始化
sz = n;
for (int i = 0; i < sz; i++) {
p[i] = i;
rank[i] = 0;
}
}
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x])); //将find(p[x])的值(即根)赋给p[x],路径压缩
}
void unin(int x, int y) {
link(find(x), find(y)); //合并两个集合，且保存集合根为其中的根节点之一
}
void compress() {
for (int i = 0; i < sz; i++)
find(i);
}
};