菜鸡的题解004——修改数组

解题思路:

并查集，按秩排序。

记得数组开大一点，An的最大值在一百万左右（我只开了二十万，不知道咋就过了）

参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N=200010;
int n,a[N],b[N];

void read(int &x){
	int f=1;x=0;char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	if(f==-1)x*=-1;
}
int c(int x){
	if(b[x]!=x)b[x]=c(b[x]);
	return b[x];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=N;i++)b[i]=i;
    for(int i=1;i<=n;i++){
    	read(a[i]);
	}
    for(int i=1;i<=n;i++){
    	a[i]=c(a[i]);
    	b[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}