123456倍


私信TA

用户名:h1910819075

访问量:2421

签 名:

AC 总在意料之外

等  级
排  名 135
经  验 7289
参赛次数 6
文章发表 6
年  龄 0
在职情况 学生
学  校 贺州学院
专  业

  自我简介:

解题思路:
使用并查集,先是初始化父亲数组,每找到一个,对父亲数组的内容加一。
注意事项:
在寻找的函数中,如果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;
}


 

0.0分

0 人评分

  评论区