AcWing 1242. 修改数组(并查集维护数组上的连通块)(广义并查集,总之是达成路径压缩)
原题链接
中等
作者:
逸误
,
2024-04-10 14:58:23
,
所有人可见
,
阅读 7
//广义上的并查集:用find函数路径压缩的思路是一样的!
//使用:单链表式的并查集
//普通并查集:p[i]:i的父节点,find(i):i所在集合的代表元素
//单链表并查集:p[i]:i的下一个结点,find(i):i向右找,第一个没有用过的元素
//为什么算是并查集呢?一样使用了路径压缩的思想
#include <iostream>
using namespace std;
const int N = 1100005;//最差情况所有数字1e6,每个数依次+1
int n;
int p[N];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n;
for(int i=0;i<N;i++)
p[i]=i;//一样地初始化并查集数组
//如果p[x]==x说明这个数还没有被用过
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
a=find(a);//找到了a后面第一个没用过的数
printf("%d ",a);
p[a]=a+1;//这里将a设置为有父亲状态即可
//下次find的时候会把p[a]更新到find(a+1)的
}
return 0;
}