前言：做这道题的时候，第一感觉很简单，但是读完题的时候很蒙，一开始没弄明白合根植物的意思，之后就是没有好的方法去处理计算合根植物的个数，百度之后才知道要用并查集这个数据结构，之前没有了解过，就花了时间去学习，搞懂之后才发现原来就是并查集啊，使用并查集根本就不需要考虑那么多，直接计算有多少个阵营（这道题里面应该是所有合根植物聚合之后的大的合根植物的个数），当然之前有接触这个并查集的大佬们，这道题很简单，但是没有学过这个的，应该很难处理这道题。具体不清楚并查集的可以看下篇博客 https://www.cnblogs.com/henuliulei/p/10546264.html
思路：看上面的参考图，要求的是合根的个数，其实就是连通子集的个数，注意6也是一个连通子集，使用并查集可以快速求出连通子集，但要注意算法的压缩。注意因为m，n取值较大，所以考虑
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int MAX = 0x3f3f3f;
4 int pre[MAX];
5 int m,n;
6 int s;
7 int left1,right1;
8 void init(int n){
9 for(int i=1;i<=n;i++){
10 pre[i]=i;
11 }
12 }
13 int find_pre(int key)
14 {
15 int temp=key;
16 while(temp!=pre[temp]){
17 temp=pre[temp];
18 }
19 int t=0;
20 while(key!=temp){//压缩
21 t=pre[key];
22 pre[key]=temp;
23 key=t;
24 }
25 return temp;
26 }
27
28 void unite(int x,int y)
29 {
30 int rootx=find_pre(x);
31 int rooty=find_pre(y);
32 if(rootx!=rooty) pre[rootx]=rooty;
33
34 }
35 int main()
36 {
37 cin >> m >> n;
38 int all=m*n;
39 cin >> s;
40 init(all);
41 for(int i=1;i<=s;i++){
42 cin >> left1 >> right1;
43 unite(left1,right1);
44 }
45
46 int att[MAX];
47 int num=0;
48 memset(att,0,sizeof(att));
49 for(int i=1;i<=all;i++){
50 att[find_pre(i)]=1;
51 }
52 for(int i=1;i<=all;i++){
53 if(att[i]==1) num++;
54 }
55 cout << num;
56 return 0;
57 }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////补充知识
- 0x3f3f3f3f的十进制是1061109567，也就是10^9级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
- 另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。
- 最后，0x3f3f3f3f还能给我们带来一个意想不到的额外好处：如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))这样的代码来实现（方便而高效），但是当我们想将某个数组全部赋值为无穷大时（例如解决图论问题时邻接矩阵的初始化），就不能使用memset函数而得自己写循环了（写这些不重要的代码真的很痛苦），我们知道这是因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0，现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。
所以在通常的场合下，const int INF = 0x3f3f3f3f;真的是一个非常棒的选择。
