题目描述
使用并查集存入下一个要找的点的值
因为数据范围尽量使用scanf和printf
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
int p[N];
int n;
int a[N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
for(int i=0;i<=N;i++)
p[i]=i;
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
scanf("%d", &a[i]);
}
for(int i=1;i<=n;i++)
{
int pa=find(a[i]);//第一个点可以直接存
printf("%d ",pa);
p[pa]=pa+1; //存入下一个值,如果下一个值改变就递归找到最终的值
}
puts("");
}