树的应用—并查集

并查集是一种简单的集合表示
使用树的双亲表示法作为并查集的存储结构，通常使用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数

操作如下

• 将集合中的所有元素初始化为只有一个单元素的子集合

  
  
  初始化
  

  当集合变为一下情况时，存储结构变化如下

  
  

0的树上共有四个元素，所以0位置的双亲值为4，因为是根结点，值为-4。
3的双亲结点为2，所以双亲值为2。
剩余元素以此类推

代码实现并查集的操作
这里的S数组存储的是并查集里双亲结点的下标

#define SIZE 100
int  UFset[SIZE]

void Initial(int S[]){
    for (int i = 0; i < size; ++i)
    {
        S[i] = -1;
    }
}

int Find(int S[],int x){//要找出的是x元素所在树的根结点，因为根结点双亲值为负
    while(S[x]>=0)
        x = S[x];
    return x;
}


void Union(int S[],int Root1,int Root2){//合并就是把Roo2子集变为Root1的子集
    S[Root2] = Root1;
}

合并操作图解

Root1为0，Root2为1
合并操作之后S数组的变化