一、并查集
（一）定义
并查集是一种使用树型结构来表示集合关系的数据结构。
（二）基本操作
查：Find(S[],x)
并：Union(S[],root1,root2)
（三）存储结构
1、基本实现
并查集的实现可以使用树的实现方式。

typedef struct{
    ElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MaxSize];
    int Length;
}PTree;

2、基本操作
（1）初始化

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

(2)查

int Find(int S[],int x){
    int root=x;
    while(S[root]>=0)
    {
        root=S[root];
    }
    while(x!=root)
    {
        int t=S[x];
        S[x]=root;
        x=t;
    }
    return root;
}

（3）并

bool Union(int S[],int Root1,int Root2){
    if(Root1==Root2)
    {
        return false;
    }
    if(S[Root1]>S[Root2])
    {
        S[Root1]+=S[Root2];
        S[Root2]=Root1;
    }
    else
    {
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
    return true;
}