算法1

并查集的高级用法

O（n + m）

C++ 代码

#include<cstdio>
using namespace std;

const int N = 1000010;

int p[N];

int n;

int a[N];

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

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