解题思路:
使用并查集,先是初始化父亲数组,每找到一个,对父亲数组的内容加一。
注意事项:
在寻找的函数中,如果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 人评分
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:625 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:516 |
简单的a+b (C语言代码)浏览:535 |
【计算两点间的距离】 (C语言代码)浏览:879 |
【绝对值排序】 (C++代码)浏览:669 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:738 |
三角形 (C++代码)递推浏览:755 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:667 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:1111 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:509 |