[蓝桥杯2019年第十届省赛真题-修改数组] 并查集(路径压缩)

#include

using namespace std;

const int N = 1000010;

int p[N], a[N];

int find(int x) {

    if (x != p[x]) p[x] = find(p[x]);

    return p[x];

}

int main(void) {

    int n;

    scanf("%d", &n);

    for (int i = 1; i <= N; i++) p[i] = i;

    for (int i = 1; i <= n; i++) {

        scanf("%d", &a[i]);

    }

    for (int i = 1; i <= n; i++) {

        int father = find(a[i]);

        printf("%d ", father);

        p[father] = father + 1; 

    }

    return 0;

}