题目内容:

image-20210312222713760

题目分析:

这道题可以采用并查集的方式做,会用并查集会感觉非常简单。

然而,我不会。最初按照自己的思路走了两边,都过不了。后面百度说用并查集,又专门去学了下并查集,然后重构代码,过了。

这道题用并查集思路很清晰。题目已说明,给定的两个格子的植物会合为一颗植物,这就是两个集合合并为一个集合的过程,我们最终要求的是有多少颗植物,也就是最终会有多少个集合。

最初状态,园子中有m×n个格子,也就是有m×n颗植物,记录为sum=m×n。

当在依次读入数据的时候,每两颗植物合为一颗,园子中的植物就会减少1,记录下sum=sum-1,最终处理完所有数据之后,剩余的植物数就是要求的结果,也就是有多少个集合。

但是,要注意,在这个过程中,给定的数据不一定都会使植物数量减少。因为当一颗大植物中的两个分支合并的时候其实他们是属于同一颗植物的,这种情况sum不应该减1。

所以我们要做的就是,读入k组数据,分别判断给出的两个格子的根节点是否相同,相同则表示为同一个植物的两个分支,这时sum不变化。如果不相同,那说明不是同一课植物,这时应该更新根节点,把其中一个集合的根节点的父节点置为另一个集合的根节点,代表两个集合的合并,即两颗植物合根为一颗,这时sum应该减去1。

下面是AC代码:

代码:

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
#include <iostream>
using namespace std;

int node[1000005];
int findF(int n){
if(node[n]==n)
return n;
else{
return findF(node[n]);
}
}

int main() {
int m,n,k,a,b,sum=0;
cin>>m>>n>>k;
for(int i=1;i<=m*n;i++){
node[i]=i;
}
sum=m*n;
for(int i=1;i<=k;i++){
cin>>a>>b;
int x=findF(a),y=findF(b);
node[a]=x;
node[b]=y;
if(x!=y) {
node[x]=y;
sum--;
}
}
cout<<sum<<endl;
return 0;
}