struct DSU {
    vector<int> parent;  // parent[i] 表示i的父节点（上级）
    vector<int> rank;    // rank[i] 表示以i为根的树的近似高度（秩）

    // 构造函数：初始化n个元素，每人独立
    DSU(int n) {
        parent.resize(n);          // 分配n个位置
        rank.resize(n, 0);         // 初始秩都为0
        for (int i = 0; i < n; i++) {
            parent[i] = i;         // 每个人都是自己的根
        }
    }
};

int find(int x) {
    while (parent[x] != x) {
        x = parent[x];     // 往上找上级
    }
    return x;
}

int find(int x) {
    if (parent[x] != x) {                 // 如果x不是根
        parent[x] = find(parent[x]);       // 递归找根，并压缩路径
    }
    return parent[x];                     // 返回根
}

void unite(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) return;       // 已经在同一个集合
    parent[rx] = ry;            // 把rx接到ry下面（或者反过来）
}

void unite(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) {
        parent[rx] = ry;            // rx的秩小，把rx接到ry上
    } else if (rank[rx] > rank[ry]) {
        parent[ry] = rx;            // ry的秩小，把ry接到rx上
    } else {
        parent[ry] = rx;            // 秩相等，接到任一个，另一个秩+1
        rank[rx]++;                 // 新根的秩增加
    }
}

#include <iostream>
#include <vector>
using namespace std;

struct DSU {
    vector<int> parent;  // 父节点数组
    vector<int> rank;    // 秩数组（近似高度）

    // 初始化：n个元素，每人独立
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 自己就是根
        }
    }

    // 查找根，带路径压缩（递归版）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    // 合并两个集合，按秩合并
    void unite(int x, int y) {
        int rx = find(x);   // 找x的根
        int ry = find(y);   // 找y的根
        if (rx == ry) {
            return;         // 已经在同一集合，无需合并
        }
        // 确保rx是秩较小的根，方便统一操作
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;       // 小树接在大树下
        } else if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
        } else {
            parent[ry] = rx;       // 秩相等，任意接一个，秩+1
            rank[rx]++;
        }
    }

    // 判断两个元素是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 7; // 0~6号同学
    DSU dsu(n);

    // 添加朋友关系（合并操作）
    dsu.unite(0, 1); // 0和1是朋友
    dsu.unite(1, 2); // 1和2是朋友 → 0,1,2成为一组
    dsu.unite(3, 4); // 3和4是朋友
    dsu.unite(5, 6); // 5和6是朋友
    dsu.unite(4, 5); // 4和5是朋友 → 3,4,5,6成为一组

    // 查询
    cout << "0和2是否在同一组？" << (dsu.same(0, 2) ? "是" : "否") << endl; // 是
    cout << "0和3是否在同一组？" << (dsu.same(0, 3) ? "是" : "否") << endl; // 否
    cout << "2和6是否在同一组？" << (dsu.same(2, 6) ? "是" : "否") << endl; // 否

    // 计算一共有几个朋友圈（即根节点个数）
    int groups = 0;
    for (int i = 0; i < n; i++) {
        if (dsu.find(i) == i) {   // 如果自己是根，就是一个集合的代表
            groups++;
        }
    }
    cout << "总共有 " << groups << " 个朋友圈。" << endl; // 应该输出2：{0,1,2} 和 {3,4,5,6}

    // 输出每个同学所属的根（代表）
    cout << "每个同学的根节点：";
    for (int i = 0; i < n; i++) {
        cout << dsu.find(i) << " ";
    }
    cout << endl; // 例如：0 0 0 3 3 3 3 （树根可能因合并顺序不同，但同一组根相同）

    return 0;
}

0和2是否在同一组？是
0和3是否在同一组？否
2和6是否在同一组？否
总共有 2 个朋友圈。
每个同学的根节点：0 0 0 3 3 3 3