解题思路:
并查集题,首先了解并查集,统计集合数用一个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 人评分
数列 (C++代码)浏览:671 |
简单的a+b (C语言代码)浏览:745 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:651 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:545 |
字符串对比 (C语言代码)浏览:1426 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:721 |
求组合数 (C语言代码)浏览:1175 |
WU-蓝桥杯算法提高VIP-Quadratic Equation (C++代码)浏览:1762 |
简单的a+b (C语言代码)浏览:536 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1433 |