蓝桥杯：合根植物

合根植物【并查集】

题目描述

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

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

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

输入描述

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

接下来一行，一个整数 k (0≤k≤10⁵ )，表示下面还有 k 行数据。

接下来 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
1
2
3
4
5

输出描述

输出植物数量。

输入输出样例

示例

输入

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出

5
1

样例说明

其合根情况参考下图：

思路：

这题考的是最简单的并查集，并查集就是，一个集合里一开始只有一颗元素，就是本身，例如题目中的植物一样，一开始
自己一个就是一个集合，然后输入许多组有连根的植物，把所有连在一个根上的植物放到一个集合中，问一共有几个集合。还有
一个比喻讲就是，一帮强盗，输入许多组两个是一伙的强盗，问你一共有多少个团伙。这都是一类问题。

• 并查集的实现分三步：
  1、初始化
  2、查找
  3、合并
  对于这个问题，我们先定义一个数组用于存放每个植物的主根，数组的下标是植物的编号，先将植物的主根定义为自己，就是
  第一步初始化。接下来输入许多组连根的植物，查找两个植物的主根，将两个植物的主根连在一起，那么和这两个主根相连的植物
  就在一个集合里了。不断对输入的两个植物进行连根。到最后遍历数组，如果一个植物的主根是本身，即f[i]==i，则这个植物就是
  主根，就算一个植物。

• 并查集最重要的就是：路径压缩，这样可以节省时间，如果不压缩，那么一个集合里植物之间的关系就成一个长链了
  变成一层一层的关系了，例如 1 -> 2 -> 3 -> 4 ,1植物的主根是2，2是3，3是4，对于 1 来说要找主根需要找三次，如果数据
  多了，会变得很慢，在 find 函数中 f[v]=find(f[v]) 就是路径压缩，在递归找主根时随便把集合里的每个植物的主根直接改成
  集合里的大主根，就是将1，2，3植物都改成 4 .大大节约了时间。

代码：

#include
int f[1000001];
int n,m;

void init()
{   //初始化 
	for(int i=1;i<=n*m;i++)
		f[i]=i;  //每个植物还没连根 
	return ;
}

int find(int v)
{   //查找 
	if(f[v]==v) 
		return v;
	else 
	{
		f[v]=find(f[v]);
		return f[v];
	}
}

void merge(int v,int u)
{   //合并 
	int t1,t2;
	t1=find(v);  //找到一个植物的主根，也就是共同的祖先 
	t2=find(u);
	if(t1!=t2)  //如果两个植物的祖先不一样 
		f[t1]=f[t2];  //则将两个植物的祖先连在一起，也可以写成 f[t2]=f[t1],都一样 
	return ;
}

int main()
{
	int x,y,k,sum=0;
	scanf("%d %d",&n,&m);  //输入行数、列数 
	scanf("%d",&k); 
	init();   //将数组 f 初始化，开始每个植物只和自己连根 
	while(index--) 
	{
		scanf("%d %d",&x,&y);
		merge(x,y);  //合并连根植物 
	}
	for(int i=1;i<=n*m;i++)  //遍历每个植物 
		if(f[i]==i)   //如果一个植物连根还是自己，则算一个植物 
			sum++;   
	printf("%d",sum);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49