一、概念：
其结构类似于树林，存储了多个互不相干的树，每棵树的根节点代表着这棵树的全部节点
二、作用：
1.查询(find)：查询两个元素是否在同一集合
2.合并(union)：将两不相交集合合并为一个集合
三、基操：
1.初始化：fa[u]表示节点u的父节点，初始化时fa[u]=u。
2.查询：看根节点是否相同。
（1）路径压缩：o(nlogn)在查询的过程中将所有节点都指向根节点，这样就导致它不能保持一开始树的形态，但是能在一次查询中改变多个节点，后续查询更便捷，因此可持久化并查集等修改代价较高的情况。
3.合并：相当于把两棵树合并起来，也就是公用同一个根节点。
（1）按秩合并、按秩合并：o(nk)将其中一个深度较小的树的根节点的父节点修改为另一个根节点。（为了避免树退化为链式结构，非特殊情况一般为节点个数比较少的，类似连通块）
例题1： 修改数组
输入：
5
2 1 1 3 4
输出：
2 1 3 4 5
分析：题意与并查集非常像，最后是要输出每个数的跟节点，如果这个数没有出现过，也就是自成一个集合，也就是自己就是自己的根节点，那么输出它本身；如果一个数在前面出现过，则输出 重复数字+1，直到不重复。所以首先初始化，使在0~N范围内所有数的根节点都为本身，接着再依次输入a[i],求其根节点，并且需要将这个数的根节点fa[a[i]]改为fa[a[i]+1],这样一来，如果后面有与a[i]相同的数出现，直接查询其根节点即可得到正确答案。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,fa[N],a[N];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<N;i++)
fa[i]=i;
for(int i=0;i<n;i++)
{
cin>>a[i];
a[i]=find(a[i]);
fa[a[i]]=find(a[i]+1);
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}