并查集（藍橋杯試題 合根植物）

問題描述

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;
}