并查集（按秩合并，路径压缩）

    并：Union：合并：合并两个不同的集合；
    查：Find：查找：判断两个集合是否在一个集合；
    集：Set：集合；

/**
    并：Union：合并：合并两个不同的集合；
    查：Find：查找：判断两个集合是否在一个集合；
    集：Set：集合；
*/
 
/**
#include 
 
using namespace std;
 
#define MAXN 1000
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MAXN];
 
SetName FindFather(SetType S,ElementType x); //查找x所属元素的集合；
void Union(SetType S,SetName root1,SetName root2); //合并两个不同的集合
 
int main()
{
    int n;
    cin >> n;
 
    return 0;
}
 
SetName FindFather(SetType S,ElementType x); //查找x所属元素的集合；
{
    while(S[x]>=0)
        x=S[x];
    return x;
}
 
void Union(SetType S,SetName root1,SetName root2); //合并两个不同的集合
{
    root1=FindFather(S,root1);
    root2=FindFather(S,root2);
    if(root1!=root2)
        S[root1]=root2;
}
*/

 2)按秩合并集合,对Union进行优化；

/**
    2)按秩合并集合,对Union进行优化；
*/
 
/**
    并：Union：合并：合并两个不同的集合；
    查：Find：查找：判断两个集合是否在一个集合；
    集：Set：集合；
*/
 
/**
#include 
 
using namespace std;
 
#define MAXN 1000
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MAXN];
 
SetName FindFather(SetType S,ElementType x); //查找x所属元素的集合；
void Union(SetType S,SetName root1,SetName root2); //合并两个不同的集合
 
int main()
{
    int n;
    cin >> n;
 
    return 0;
}
 
SetName FindFather(SetType S,ElementType x) //查找x所属元素的集合；
{
    while(S[x]>=0)
        x=S[x];
    return x;
}
 
void Union(SetType S,SetName root1,SetName root2) //合并两个不同的集合
{
    root1=FindFather(S,root1);
    root2=FindFather(S,root2);
    if(root1!=root2)
    {
        if(S[root1]
        {
            S[root1]+=S[root2];
            S[root2]=root1; //将root2（矮树）挂在root1（高树）上；
        }
        else if(S[root2]
        {
            S[root2]+=S[root1];
            S[root1]=root2;
        }
    }
}
*/

3）路径压缩：将集合的每个子孩子的父亲节点都设置为根节点；
    以便为后面的Find函数减低查找时间；对Find进行优化；

 
/**
    3）路径压缩：将集合的每个子孩子的父亲节点都设置为根节点；
    以便为后面的Find函数减低查找时间；对Find进行优化；
*/
 
/**
    并：Union：合并：合并两个不同的集合；
    查：Find：查找：判断两个集合是否在一个集合；
    集：Set：集合；
*/
 
 
#include 
 
using namespace std;
 
#define MAXN 1000
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MAXN];
 
SetName FindFather(SetType S,ElementType x); //查找x所属元素的集合；
void Union(SetType S,SetName root1,SetName root2); //合并两个不同的集合
 
int main()
{
    int n;
    cin >> n;
 
    return 0;
}
 
SetName FindFather(SetType S,ElementType x) //查找x所属元素的集合；
{
    if(S[x]<0)
        return x;
    else
        return S[x]=Find(S,S[x]);
}
 
void Union(SetType S,SetName root1,SetName root2) //合并两个不同的集合
{
    root1=FindFather(S,root1);
    root2=FindFather(S,root2);
    if(root1!=root2)
    {
        if(S[root1]//如果集合root1的元素要多一点
        {
            S[root1]+=S[root2];
            S[root2]=root1; //将root2（矮树）挂在root1（高树）上；
        }
        else if(S[root2]
        {
            S[root2]+=S[root1];
            S[root1]=root2;
        }
    }
}