蓝桥杯2019年第十届真题-修改数组 题解

解题思路:
使用并查集，先是初始化父亲数组，每找到一个，对父亲数组的内容加一。
注意事项:
在寻找的函数中，如果fa数组的内容不是要寻找的x时，要将父亲数组修改为：fa[x]=find(fa[x]);这是路劲压缩，可以使程序的运行时间变得更快，减少了不必要的路劲搜索的过程。

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100000+100;
int fa[2*N],a[N];

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

inline void pre(int k)
{
	for(int i=1;i<=2*k;i++)
		fa[i]=i;
}

int main()
{
	int n;
	scanf("%d",&n);
	pre(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++)
	{
		int fat=find(a[i]);
		printf("%d ",fat);
		fa[fat]=fa[fat]+1;
	}
	return 0;
}