class DSU {
vector<int> parent;
vector<int> rank;
public:
DSU(int n) : parent(n), rank(n) {
for(int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
int find(int x) {
if(parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
void merge(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if(rank[root_x] <= rank[root_y]) {
parent[root_x] = root_y; // 以较高的树作为新的根结点,高度相等,以root_y作为新的根结点
} else {
parent[root_y] = root_x;
}
if(rank[root_x] == rank[root_y] && root_x != root_y) {
rank[root_y]++; // 高度相等时,上面的选择以root_y作为根结点,所以rank[root_y]++
}
}
};