题目

解析

首先先让所有的f（i）=i，即每个人最开始的祖先都是自己，然后就每一次都让轮到那个数的父亲+1，第二次出现的时候就直接用父亲替换掉

并查集适用场景

1.快速合并与查询：需要频繁合并集合（如标记某个数已被占用）和查询根节点（找下一个可用位置）。
2.路径压缩优化：通过压缩查找路径，使得后续查询接近常数时间复杂度。
3.动态维护连续区间：每个数字的父节点指向下一个可用位置，天然维护了一个动态递增的区间。

代码

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n;
int f[1000010];int find(int x) {if (f[x] == x)return x;return f[x] = find(f[x]);
}int main() {cin >> n;for (int i = 0; i <= 1e6; i++)f[i] = i;for (int i = 0; i < n; i++) {int x;cin >> x;x = find(x);f[x] = find(x) + 1;cout << x << ' ';}return 0;
}