并查集（蓝桥杯试题 合根植物）

问题描述

w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。

　　这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入格式

第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。

　　接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)

　　接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

　　比如：5 * 4 的小格子，编号：

　　1 2 3 4

　　5 6 7 8

　　9 10 11 12

　　13 14 15 16

　　17 18 19 20

样例输入

5 4

16

2 3

1 5

5 9

4 8

7 8

9 10

10 11

11 12

10 14

12 16

14 18

17 18

15 19

19 20

9 13

13 17

样例输出

5

样例说明

　　其合根情况参考下图

# include<cstdio>
# include<cmath>
# include<iostream>
# include<string>
# include<algorithm>
# include<set>
# include<vector>

using namespace std;

class DisjSet {
private:
	vector<int> parent;
	vector<int> rank;

public:
	DisjSet(int max_size) :parent(vector<int>(max_size)), rank(std::vector<int>(max_size, 0))
	{
		for (int i = 1; i < max_size; i++)
			parent[i] = i;
	}
	int find(int x) {
		return x == parent[x] ? x : (parent[x] = find(parent[x]));
	}
	void to_union(int x1, int x2)
	{
		int f1 = find(x1);
		int f2 = find(x2);
		if (rank[f1] > rank[f2])
			parent[f2] = f1;
		else
		{
			parent[f1] = f2;
			if (rank[f1] == rank[f2])
				++rank[f2];
		}
	}
	bool is_same(int e1, int e2)
	{
		return find(e1) == find(e2);
	}
	int count_set() {
		vector<int> sets(parent.size(),0);
		int result = 0;
		for (int i = 1; i < parent.size(); i++) {
			//使用find进行寻找
			//在合并后，因为一个集合内点都指向旧的parent x，然后这个旧的parent x指向新的parent x，就会出现重复计算。
			//使用find寻找，让一个集合内所有元素指向同一个parent x
			if (sets[find(i)] == 1)
				continue;
			else
			{
				sets[find(i)] = 1;
				result += 1;
			}
		}
		return result;
	}
};

int main() {
	int row,column;
	int ways_count;
	vector<int*> ways;
	//数据读入
	cin >> row;
	cin >> column;

	cin >> ways_count;
	for (int i = 0; i < ways_count; i++) {
		int* node = new int[2];
		cin >> node[0];
		cin >> node[1];
		ways.push_back(node);
	}
	//初始化，每个格子都是一株,0号格子为空
	DisjSet all_set(row*column + 1);
	//遍历
	for (vector<int*>::iterator it = ways.begin(); it != ways.end(); it++) {
		int one = (*it)[0];
		int two = (*it)[1];
		all_set.to_union(one, two);
	}
	cout << all_set.count_set()<< endl;
	cin.get();
	cin.get();
	return 0;
}