蓝桥杯2017年第八届真题-合根植物 （C++代码）

解题思路:
并查集题，首先了解并查集，统计集合数用一个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;
}