解题思路:
并查集题,首先了解并查集,统计集合数用一个bool型数组isRoot[maxn]记录每个结点是否作为某个数的根节点,当处理完数据之后就可以遍历所有元素,令他所在集合的根结点 为true,最后累加就能得到根节点数(即植物株数)。
注意事项:
一定要初始化
参考代码:
#include <cstdio> using namespace std; const int maxn = 1e+6 + 10; int father[maxn]; bool isRoot[maxn]; int findFather(int x){ int a = x; while(x != father[x]){ x = father[x]; } while(a != father[a]){ int z = a; a = father[a]; father[z] = x; } return x; } void Union(int a, int b){ int faA = findFather(a); int faB = findFather(b); if(faA != faB){ father[faA] = faB; } } void init(int n){ for(int i = 1; i <= n; i++){ father[i] = i; isRoot[i] = false; } } int main(void){ int m,n,k,a,b; scanf("%d%d%d", &m, &n, &k); init(m*n); for(int i = 0; i < k; i++){ scanf("%d%d",&a,&b); Union(a,b); } for(int i = 1; i <= m*n; i++){ isRoot[findFather(i)]= true; } int ans = 0; for(int i = 1; i <= m*n; i++){ if(isRoot[i] == true) ans++; } printf("%d", ans); return 0; }
0.0分
1 人评分
浏览:621 |
字符逆序 (C语言代码)浏览:452 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:515 |
C二级辅导-公约公倍 (C语言代码)浏览:863 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:720 |
The 3n + 1 problem (C语言代码)浏览:1368 |
化学品问题 (C语言代码)浏览:1378 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:763 |
C语言训练-求矩阵的两对角线上的元素之和 (C语言代码)浏览:613 |
计算质因子 (C++代码)浏览:1777 |