#include<iostream>
using namespace std;
const int N =100010;
int parent[N],Rank[N];//储存元素的父节点
void Build(int n)//建立由n个单元元素构成的并查集
{
    for(int i=1;i<=n;i++)
    parent[i]=i;
}
//1.查找并返回根结点(非优化版本)
// int Find(int x)
// {
//     if(parent[x]!=x)  return Find(parent[x]);
//     return x;
// }





//2.带有路径压缩的优化
int Find(int x)
{
    if(parent[x]!=x)  parent[x]=Find(parent[x]);
    return parent[x];
}


1.合并两个集合
void Union(int x,int y)
{
    parent[Find(y)]=Find(x);
}




2.按秩合并  秩：指树的高度  按秩合并就是在合并的过程中总是将高度小的树根指向高度大的
void Union(int x,int y)
{
    x=Find(x),y=Find(y);
    if(x==y)  return;
    if(Rank[x]<Rank[y])  parent[x]=y;
    else 
    {
        parent[y]=x;
        if(Rank[y]==Rank[x]) Rank[x]++;
    }
}





int main()
{

    return 0;
}

一般在实际应用中使用按秩合并和路径压缩一种就可以了