备战蓝桥杯决赛----坚持第六天！！！

     今天的学习时间是从晚6点开始，一道简单的题目，消耗了我三个半小时，其实是先看了一道关于hash的题目，没有看懂，就用看了一道题目，正好碰到了简单的并查集。虽然今天也是很苦逼，但是心情似乎没有那么差了，也许是我来学习之前就想明白了，不想说自己生活上的事情，我们单单对于算法来讲，千万不要因为你没有AC一道题目，没有看懂一道题目的解析而感到沮丧，伤心。。更不能把这种情绪带到生活的其他方面。反而我们可以通过其他事情，来缓和我们对于没有AC的沮丧心情。

题目：

问题描述

　　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

样例说明

　　其合根情况参考下图

刚开始我也是没有思路，然后百度，看到其他博主对此题分析的第一句话，都是简单，并查集操作。然后我就立刻停止了浏览，自己写了起来，因为自己之前看过并查集，感觉再回忆一下，应该能AC这题。所以我又理了一遍并查集，如果有不懂并查集的，可以先跳过下面的答案，看看我下面并查集的构建过程。

代码：

#include<iostream>
using namespace std;
const int MAX=1000001;//数组范围一定要明确 
int parent[MAX];
int rank[MAX];
int find(int p){
     while(parent[p]!=p){
      	parent[p] = parent[parent[p]];
        p=parent[p];
		}
		return p;
}
void uniono(int p,int q){
     int pID = find(p);
	 int qID = find(q);
	 if(pID==qID){
	 	return;
	 }
	 if(rank[pID]>rank[qID]){
	 parent[qID]=pID;	
	 }else if(rank[pID]<rank[qID]){
	 	parent[pID]=qID;
	 }else{
	 	parent[qID]=pID;
	 	rank[pID]+=1;
	 }
	 	
}
int main(){
	int m,n;
	cin>>m>>n;
	int k=m*n;
	for(int i=1;i<=k;i++){
		parent[i]=i;
		rank[i]=1;
	}
    int x,y,l;
    cin>>l;
    for(int i=0;i<l;i++){
    	cin>>x>>y;
    	uniono(x,y);
	}
	int *p = new int[k+1];
	for(int i=1;i<=k;i++){
		p[find(i)]=1;//这里之前写成parent[i]就一直不能通过，改为find(i)后可以通过，至于原因，想到再说吧 
	}
	int s=0;
	for(int i=1;i<=k;i++){
		if(p[i]==1){
			s+=1;
		}
	}
	cout<<s;
	return 0;
}

并查集的构建，关键在于需要设置两个方法：uniono（合并）与find（查找）

原始的简单方法：

int id[10];//构建一个id数组，用于表示节点间的关系。如：数组奇数元素定义为0，偶数元素定义为1，则表示奇数元素节点互相相连，偶数元素节点互相相连
int find(int p){
	return id[p];
}
void uniono(int p,int q){
     int pID = find(p);
	 int qID = find(q);
	 if(pID==qID){
	 	return;
	 }else{
	 	id[pID]=id[qID];
	 }	
}

采用父节点的思想，所有连接节点属于一个父节点

int parent[10];
int find(int p){
     while(parent[p]!=p){
       p=parent[p];
		}
 return p;
}
void uniono(int p,int q){
     int pID = find(p);
	 int qID = find(q);
	 if(pID==qID){
	 	return;
	 }
	 parent[pID]=qID;	
}

基于rank的优化

int parent[10];
int rank[10];
int find(int p){
     while(parent[p]!=p){
       p=parent[p];
		}
	return p;
}
void uniono(int p,int q){
     int pID = find(p);
	 int qID = find(q);
	 if(pID==qID){
	 	return;
	 }
	 if(rank[pID]>rank[qID]){
	 parent[qID]=pID;	
	 }else if(rank[pID]<rank[qID]){
	 	parent[pID]=qID;
	 }else{
	 	parent[qID]=pID;
	 	rank[pID]+=1;
	 }
	 	
}

路径压缩：

int parent[10];
int rank[10];
int find(int p){
     while(parent[p]!=p){
       	p = parent[parent[p]];
       p=parent[p];
		}
		return p;
}
void uniono(int p,int q){
     int pID = find(p);
	 int qID = find(q);
	 if(pID==qID){
	 	return;
	 }
	 if(rank[pID]>rank[qID]){
	 parent[qID]=pID;	
	 }else if(rank[pID]<rank[qID]){
	 	parent[pID]=qID;
	 }else{
	 	parent[qID]=pID;
	 	rank[pID]+=1;
	 }
	 	
}