【并查集】蓝桥杯·修改数组题解

题意

给定一个长度为 $N$ 的数组 $A=[A_1,A_2,⋅⋅⋅,A_N]$，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 $A_2,A_3,⋅⋅⋅,A_N$。

当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1∼A_{i−1}$ 中出现过。

如果出现过，则小明会给 $A_i$ 加上 $1$；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 $1$，直到 $A_i$ 没有在 $A_1∼A_{i−1}$ 中出现过。

当 $A_N$ 也经过上述修改之后，显然 $A$ 数组中就没有重复的整数了。

现在给定初始的 $A$ 数组，请你计算出最终的 $A$ 数组。

思路

还以为是个什么数据结构，实际上直接并查集就可以了，每个数一开始都是自己的集合，那么属于这个集合的父亲节点就可以。
为什么是这样的呢？我们来分析分析：

一开始都为各个单独的集合，x和x+1，这个时候我来了一个x，那么输出什么？肯定是x（输出fa[x])，这个时候是可以的，然后！将fa[x]=x+1，这个时候这个集合有两个元素{x,x+1}，那么下次来x会怎么样？输出这个集合的父亲节点（此时是x+1）即可。那么这个时候怎么办？

PS：对于一个x，我们做x=find(x)，然后输出x（就是上述说的这个集合的父亲节点）

fa[ x ] = fa[ x ]+1，我们把原来整个集合，并入下一个集合当中。

可能会有疑问，假如{1,2}要fa[2]=fa[2] + 1，那么假如3也在别人的集合里面呢？{3,4,5}，那么这个集合的fa[3]=5，你将来下次find(2)的时候还是能找到5，然后输出5即可。

代码

1）我的代码
有点写复杂了，实际上是一样的

int fa[N],n,a[N];
inline int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void solve()
{
    cin>>n;
    for (int i=1;i<N;i++) fa[i]=i;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        int fx=find(a[i]),fy=find(fx+1);
        cout<<fx<<" ";
        fa[fx]=fy;
    }
}

2）y总代码（*）

#include <cstdio>

const int N = 1100010;

int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 1; i < N; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        x = find(x);
        printf("%d ", x);
        p[x] = x + 1;
    }

    return 0;
}