藍橋杯：曆屆試題 合根植物（并查集 + 索引思想）

題目：

https://blog.csdn.net/weixin_40163242/article/details/88397162

還是剛剛那道題，這次用并查集做就成功AC了。其實用并查集做完才發現，其實比廣搜做還要簡單啊！

這題簡直就是裸的并查集了，然後這題還有一個索引的思想注意一下。在最後我将所有的boss結點的tag值置為1，然後我再周遊一遍tag數組，看哪些值為1，哪些就是boss結點了，那麼問題的解實際上是等于boss結點的個數的。

AC代碼：

#include<iostream>
using namespace std;

const int maxn = 1000005;
int m, n, k;
int tag[maxn];
int parent[maxn];

//-------------------并查集----------------------
void init()
{
	for(int i = 1;i <= n * m;i++)
		parent[i] = i;
}
 
int getBoss(int x)
{
	if(x == parent[x])
		return x;
	return getBoss(parent[x]);
}

int merge(int x, int y)
{
	int boss_x = getBoss(x);
	int boss_y = getBoss(y);			//這裡之前複制的時候getBoss(x)。。。找錯找了半天，粗心啊！！ 
	parent[boss_x] = boss_y;
}

/*
judge函數本題可要可不要 
bool judge(int x, int y)
{
	int boss_x = getBoss(x);
	int boss_y = getBoss(x);
	return boss_x == boss_y;
}
*/
//------------------------------

int main()
{
	cin >> m >> n >> k;
	int ans = 0;
	init();						//初始化parent數組 
	for(int i = 1;i <= k;i++)
	{
		int a, b;
		cin >> a >> b;			//a與b存在合根關系 
		merge(a, b);			//那麼我就讓a與b merge起來
	}
	//運用索引思想，找出boss結點的個數，boss結點的個數等于關系數
	for(int i = 1;i <= n * m;i++)
	{
		tag[getBoss(i)] = 1;		//将boss結點的tag值标記為1，便于索引 
	} 
	//看tag值是否為1，就可以知道是否為boss結點了，而且也不會重複，索引思想！
	for(int i = 1;i <= n * m;i++)
	{
		if(tag[i] == 1)
			ans++;
	} 
	cout << ans << endl;
	return 0;
}