并查集在ACM比赛之中比较的常见，映象较深的是PAT团体天梯赛中，中等的题目里面必有这样一道题目，基本的模板和套路。

今日份通过左神算法学习，复习一下！

深入理解请到：

参照：

并查集解决的问题？

答：（1）判断两个元素，是否在同一个集合里面。（2）合并两个集合。

常规的解决办法是，暴力遍历，但是这并不美妙。并查集就非常之快的查找。

并查集的思路：把一个集合里面，指定一个根节点（代表元素），所有元素最终指向这个节点。就是一棵树，查的时候，向上查找根节点，如果两个元素的根节点相同，就是在同一个集合里面。合并两个集合A，B的时候（假设A的元素比B的元素数量少），就把A的元素挂在B下面，然后进行路径压缩，把B集合里面的元素指向A的根节点，路径压缩的目的是：减少查询时间，变为O(1）。

代码如下：

package class_05;import java.util.HashMap;import java.util.List;public class Code_04_UnionFind {	public static class Node {		// whatever you like	}	public static class UnionFindSet {		public HashMap
    
      fatherMap;   // 通过Map的key-value形式，来解决向上查找。		public HashMap
     
       sizeMap;  // 记录这个节点所在集合的大小		public UnionFindSet() {			fatherMap = new HashMap
      
       ();			sizeMap = new HashMap
       
        ();		}		public void makeSets(List
        
          nodes) {			fatherMap.clear();			sizeMap.clear();			for (Node node : nodes) {				fatherMap.put(node, node);				sizeMap.put(node, 1);			}		}		private Node findHead(Node node) {    			Node father = fatherMap.get(node);			if (father != node) {				father = findHead(father);			}			fatherMap.put(node, father);			return father;		}				public boolean isSameSet(Node a, Node b) {			return findHead(a) == findHead(b);		}		public void union(Node a, Node b) {			if (a == null || b == null) {				return;			}			Node aHead = findHead(a);			Node bHead = findHead(b);			if (aHead != bHead) {				int aSetSize= sizeMap.get(aHead);				int bSetSize = sizeMap.get(bHead);				if (aSetSize <= bSetSize) {					fatherMap.put(aHead, bHead);					sizeMap.put(bHead, aSetSize + bSetSize);				} else {					fatherMap.put(bHead, aHead);					sizeMap.put(aHead, aSetSize + bSetSize);				}			}		}	}	public static void main(String[] args) {		// do whatever you like	}}
        
       
      
     
    

给一个矩阵判断岛的个数，连通性问题，可以采用分块，把矩阵分块，然后用并查集感染的形式，统计岛的个数。

package class_05;public class Code_03_Islands {	public static int countIslands(int[][] m) {		if (m == null || m[0] == null) {			return 0;		}		int N = m.length;		int M = m[0].length;		int res = 0;		for (int i = 0; i < N; i++) {			for (int j = 0; j < M; j++) {				if (m[i][j] == 1) {					res++;					infect(m, i, j, N, M);				}			}		}		return res;	}	public static void infect(int[][] m, int i, int j, int N, int M) {		if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {			return;		}		m[i][j] = 2;		infect(m, i + 1, j, N, M);		infect(m, i - 1, j, N, M);		infect(m, i, j + 1, N, M);		infect(m, i, j - 1, N, M);	}	public static void main(String[] args) {		int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 				        { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, 				        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },				        { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, 				        { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 				        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },				        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };		System.out.println(countIslands(m1));		int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 						{ 0, 1, 1, 1, 1, 1, 1, 1, 0 }, 						{ 0, 1, 1, 1, 0, 0, 0, 1, 0 },						{ 0, 1, 1, 0, 0, 0, 1, 1, 0 }, 						{ 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 						{ 0, 0, 0, 0, 1, 1, 1, 0, 0 },						{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };		System.out.println(countIslands(m2));	}}