并查集的基本思想和实现

大致思想：

判定两支队伍是否属于同一个集合，方法就是看他们的最高领袖是否是同一个人。
同样的，判断两个元素是否属于同一个集合，就看他们的最高父节点是否是同一个。
然后是集合的合并，合并其实就非常简单，让其中任何一个集合的最高父节点变成另外一个集合的最高父节点的子节点，合并就完成了。
然后为了使生成的树的高度尽量低，引入了rank数组记录树的高度

实现过程

1.父节点的判定

规定，一个点的父节点如果是其自身，则该点为此集合的最高父节点。
而在一开始的时候，每一个元素都是一个独立的集合，所以每个元素的父节点都是其自身。

void Init(int *father,int *rank)
{
    for(int i=0;i<maxn;++i){
        father[i]=i;
        rank[i]=0;
    }
}

2.寻找最高父节点

利用循环，只要其值得父节点不等于本身，就可以一直回溯。
同时，为了提高寻找父节点的效率，需要进行压缩路径的处理。即让其直接指向最高父节点，提高查找效率。

方案1：

int FindSet(int x,int *father)
{
    int r=x,j;
    while(x!=father[x])//不断回溯
        x=father[x];
    while(r!=x)//路径压缩，使路径上的每一个点都指向最高父节点
    {
        j=father[r];
        father[r]=x;
        r=j;
    }
    return x;
}

方案2：

int FindSet2(int x,int *father)
{

    if(x!=father[x])
        father[x]=FindSet2(father[x],father);//利用递归代替循环，同时压缩路径，很精髓
    return father[x];
}

区间合并:

为了减少树的高度，使rank值小的树放到rank值高的树下面，作为一个分支。

void Union(int x,int y,int *father,int *rank)
{
    x=FindSet1(x,father);
    y=FindSet1(y,father);
    if(x==y)
        return ;
    if(rank[x]>rank[y])
        father[y]=x;
    else{
        if(rank[x]==rank[y])
            rank[y]++;
        father[x]=y;
    }
    return ;
}

总体代码：

#include<bits/stdc++.h>
using namespace std;
const  int maxn=1010;

void Init(int *father,int *rank)
{
    for(int i=0;i<maxn;++i){
        father[i]=i;
        rank[i]=0;
    }
}
int FindSet1(int x,int *father)
{
    int r=x,j;
    while(x!=father[x])
        x=father[x];
    while(r!=x)
    {
        j=father[r];
        father[r]=x;
        r=j;
    }
    return x;
}
int FindSet2(int x,int *father)
{

    if(x!=father[x])
        father[x]=FindSet2(father[x],father);
    return father[x];
}
bool Union(int x,int y,int *father,int *rank)
{
    x=FindSet1(x,father);
    y=FindSet1(y,father);
    if(x==y)
        return false;
    if(rank[x]>rank[y])
        father[y]=x;
    else{
        if(rank[x]==rank[y])
            rank[y]++;
        father[x]=y;
    }
    return true;
}
int main()
{
    int n,x,y;
    int father[maxn],rank[maxn];
    Init(father,rank);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x>>y;
        bool flag=Union(x,y,father,rank);
        if(flag)
            cout<<"Successful"<<endl;
        else
            cout<<"Set has exist"<<endl;
    }
    return 0;
}