P8654 [蓝桥杯 2017 国 C] 合根植物---并查集！！！

题目

并查集模板

算法核心就是
1、查找

int find(int x) {
	if (d[x] == x)
		return x;
	else
		return d[x] = find(d[x]);
	//注意这儿是一个赋值，不是判等
	//最终返回的也是一个d[x]的值
}

2、合并

void unity(int a, int b) {
	d[find(a)] = find(b);
	//注意这是先找到a,b的根，再将b的根赋给a的根
}

3、判断是否是根节点
if（d[i]==i） ans++;

4、模板

还模板！
什么都想走捷径！！
这道题就是标准的并查集题目，这道题的代码就是模板！！！！

分析

并查集（Union-Find）是一种数据结构，专门解决这种“分组”，最后问有多少个组的问题。

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>

#include <cctype>
using namespace std;
int n, m, k;
int d[1000010], q[1000010];
long long ans;
//找根
int find(int x) {
	if (d[x] == x)
		return x;
	else
		return d[x] = find(d[x]);
	//注意这儿是一个赋值，不是判等
	//最终返回的也是一个d[x]的值
}

//合并
void unity(int a, int b) {
	d[find(a)] = find(b);
	//注意这是先找到a,b的根，再将b的根赋给a的根
}

int main() {
	cin >> m >> n >> k;

	for (int i = 1; i <= n * m; i++)
		//先初始化，每个节点的根是本身
		d[i] = i;
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		unity(a, b);
		//合并2个节点的根
	}
	//找根
	for (int i = 1; i <= m * n; i++) {
		//定义q来标记根节点，避免重复添加
		if (q[find(i) ] == 0) {
			q[find(i)]++;
			ans++;
		}
	}
//找根的代码可以换成
//	for(int i=1;i<=m*n;i++){
//		if(d[i]==i) ans++;
//	}
	cout << ans << endl;
	return 0;
}