class Djset {
private:
? ? vector<int> parent;? // 記錄節(jié)點的根
? ? vector<int> rank;? // 記錄根節(jié)點的深度（用于優(yōu)化）
? ? int count;? ? ? ? // 記錄連通分量的個數(shù)
? ? int rest;? ? ? ? ? // 記錄多余的連接數(shù)
public:
? ? Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)), count(n), rest(0) {
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? parent[i] = i;
? ? ? ? }
? ? }
? ?
? ? int find(int x) {
? ? ? ? // 壓縮方式：直接指向根節(jié)點
? ? ? ? if (x != parent[x]) {
? ? ? ? ? ? parent[x] = find(parent[x]);
? ? ? ? }
? ? ? ? return parent[x];
? ? }
? ?
? ? void merge(int x, int y) {
? ? ? ? int rootx = find(x);
? ? ? ? int rooty = find(y);
? ? ? ? if (rootx != rooty) {
? ? ? ? ? ? // 按秩合并
? ? ? ? ? ? if (rank[rootx] < rank[rooty]) {
? ? ? ? ? ? ? ? swap(rootx, rooty);
? ? ? ? ? ? }
? ? ? ? ? ? parent[rooty] = rootx;
? ? ? ? ? ? if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
? ? ? ? ? ? count--;
? ? ? ? } else {
? ? ? ? ? ? rest++;
? ? ? ? }
? ? }
? ? int getCount() {
? ? ? ? return count;
? ? }
? ? int getRest() {
? ? ? ? return rest;
? ? }
};
