以下是我一直使用的并查集模板。

int p[MAX];　　// 存储父结点
int num[MAX];  // 存储当前集合元素个数

　　初始化

　　num的初始值由具体题目决定，比如对不具有自反性的关系num初始化为0，如果编号为1~n，要修改循环变量

for(i=0;i<n;i++){
    num[i]=1;
    p[i]=i;
}

　　find函数的递归实现

　　代码只有一行，但是数据大易超时。

int find(int x){
return x==p[x]?x:find(p[x]);
} 

　　find函数的非递归实现

int find(int x)
{
    int k, j, r;
    r=x;
    while(r!=p[r])   
        r=p[r];     
    k=x;        
    while(k!= r)             
    {
        j=p[k];       
        p[k]=r;     
        k=j;                 
    }
    return r;                 
}

　　Union函数：利用路径压缩合并两个集合

　　经典方法1：将小的集合合并到大的集合，只更新大集合的元素个数

void Union(int x,int y)
{
int px=find(x);
int py=find(y);
if(px==py)return;
if(num[px]>num[py]){
num[px]+=num[py];
p[py]=px;
}
else{
num[py]+=num[px];
p[px]=py;
}
}

　　经典方法2：任意将一个集合合并到另一个集合，但同时更新两个集合元素个数

void Union(int x,int y)
{
int px=find(x);
int py=find(y);
if(px!=py)
{
num[px]+=num[py];
num[py]=num[px];
p[px]=py;
}
}

　　经典方法3：不需要记录集合大小时，任意将一个集合合并到另一个集合

void Union(int x,int y)
{
int px=find(x);
int py=find(y);
if(px!=py)p[px]=py;
}

　　计算集合个数

setnum=0；
for(i=0;i<n;i++){
if(p[i]==i)setnum++;
}

　　当前元素所在集合的元素个数

num[find(x)]