并查集高效解决“全球变暖”

解题思路:

       1.首先根据并查集可以得到在地球变暖前一共有多少岛屿：事先求出一共有多少'#'，之后每合并一个就减一，最后剩的个数就是岛屿数量。并且每个岛屿的祖先都是指向了一个，这是并查集的特点；

       2.遍历所有点，找到四面都不环水的'#'，对其进行计数，因为每一座岛屿可能拥有不只一个这样的点，所以我们只对其祖先结点计数，防止重复；

       3.结果=原先岛屿-现存岛屿。

       （并查集就是一种模板，就看怎么利用了）

注意事项:

       1.这道题问的是消失了多少岛屿，注意问题，一开始我以为问现存多少岛屿耽误了时间。（得22分可能因为这个）

       2.想清楚一个问题，一个岛屿在地球变暖后可能分成两片，但还是原先的那一个岛屿，不能算成两个，我的处理就是思路里的2。（得四十多分可能是这个问题没想明白）。

参考代码:

#include<iostream>
using namespace std;
#include<cstring>
class UnionFind{
	private:
		int *p;
		int num;
		int count;
	public:
		UnionFind(int x,int c){
			num = x*x;
			p = new int[num];
			for(int i=0;i<num;i++){
				p[i] = i;
			}
			count = c;
		}
		int Find(int x){
			while(x!=p[x]){
				p[x] = p[p[x]];  // 压缩路径，可省去
				x = p[x];
			}
			return x;
		}
		void Union(int x,int y){
			int rootx = Find(x);
			int rooty = Find(y);
			if(rootx==rooty){
				return ;
			}else{
				p[rootx] = rooty;
				count--;
			}
		}
		int getCount(){
			return count;
		}
};
int main(){
	int n;
	cin>>n;
	char **dp = new char*[n];
	for(int i=0;i<n;i++){
		dp[i] = new char[n];
	}
	// 输入  
	int c = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>dp[i][j];
			if(dp[i][j]=='#'){
				c++;
			}
		}
	}
	// 画圈，将一个岛屿的'#'都指向一个祖先
	UnionFind f(n,c);
	for(int i=1;i<n-1;i++){
		for(int j=1;j<n-1;j++){
			if(dp[i][j]=='#'){
				if(dp[i][j+1]=='#'){
					f.Union(i*n+j,i*n+j+1);
				}
				if(dp[i+1][j]=='#'){
					f.Union(i*n+j,i*n+n+j);
				}
			}
		}
	}
	// 找圈内四面都不是水的'#'
	int *q = new int[n*n];
	memset(q,0,sizeof(int)*(n*n));
	for(int i=1;i<n-1;i++){
		for(int j=1;j<n-1;j++){
			if(dp[i][j]=='#' && dp[i-1][j]=='#' && dp[i+1][j]=='#' && dp[i][j-1]=='#' && dp[i][j+1]=='#'){
				int t = f.Find(i*n+j);  // 只给祖先计数，防止重复
				q[t] = 1; 
			}
		}
	}
	// 求结果 
	int sum = 0;
	for(int i=0;i<n*n;i++){
		sum += q[i];
	}
	cout<<f.getCount()-sum;
	return 0;
}