#define MAX_TREE_SIZE 10

typedef struct {
    ItemType data;
    int parent;
} PTNode;


typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;
}PTree;




#define SIZE 10;

int UFSets[SIZE];

// 初始化并查集
void init(int set[]) {
    for(int i = 0; i < SIZE; i ++ ) set[i] = -1;
}

// Find "查"操作，找到x所属集合（返回x所属根节点）
int find(int S[], int x) {
    while(S[x] >= 0) x = set[x];  // 循环找x的根
    return x;  // 根的S[]小于0
}

// Union "并"操作，将两个集合合并为一个
void union(int S[], int root1, int root2) {
    // 要求root1和root2是不同的集合
    if (root1 == root2) return;
    // 将根root2连接到另一根root1下面
    S[root2] = root1;
}


// 优化
// 查，压缩路径
int find(int S[], int x) {
    int root = x;
    while(S[root] >= 0) root = S[root];  // 循环找到根
    while(x != root) {  // 压缩路径
        int t = S[x];   // t指向x的父节点
        S[x] = root;    // x直接挂到根节点下
        x = t;
    }
    return root;
}

// 并，小树合并到大树，根节点的绝对值是当前集合结点数
void union(int S[], int root1, int root2) {
    if (root1 == root2) return;
    if (S[root1] > S[root2]) {  // root1结点数更少
        S[root2] += S[root1];   // 累加结点总数
        S[root1] = root2;       // 小数合并到大树
    }
    else {
        S[root1] += S[root2];
        S[root2] = root1;
    }
}