并查集知识整理、蓝桥杯修改数组

一、概念：

其结构类似于树林，存储了多个互不相干的树，每棵树的根节点代表着这棵树的全部节点

二、作用：

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;
 }