并查集理解

package basic_class_04;

import java.util.HashMap;
import java.util.List;

/**
 * 并查集:
 *   在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合
 *   然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
 *   
 *   并查集是一种树形结构,又叫"不相交集合",保持了一组不相交的动态集合,每个集合通过一个代表来识别
 *   代表即集合中的某个成员,通常选择根做这个代表
 *   
 * @author lenovo
 *
 */
public class UnionFind {
	
	public static class Data {
		
	}
	
	public static class UnionFindSet {
		// (k, v)  --  表示的是  k 节点的父节点是 v
		public HashMap<Data, Data> fatherMap;
		// 节点的集合的长度   其中只有代表节点的长度是有效的,其他节点的长度都是1 都是无效的
		public HashMap<Data, Integer> sizeMap;
		
		// 初始化方法
		public UnionFindSet(List<Data> nodes) {
			fatherMap = new HashMap<Data, Data>();
			sizeMap = new HashMap<Data, Integer>();
			makeSets(nodes);
		}
		
		// 你要让我使用并查集操作 前提是每一个节点各自成一个集合
		// 所以你使用并查集的条件就是  你 一开始就得把所有的集合给我
		private void makeSets(List<Data> nodes) {
			fatherMap.clear();
			sizeMap.clear();
			for(Data node : nodes) {
				// 一开始初始化的时候   每个节点的父节点都是 本身
				fatherMap.put(node, node);
				// 一开始初始化的时候  每个节点的长度就是 1
				sizeMap.put(node, 1);
			}
		}
		// 查找集合的代表节点
		/**
		 * 从一个节点找这个节点所在集合的代表节点就是一直找父节点,知道这个父节点指向的是自己
		 * 那么这个节点就是代表节点
		 * 找代表节点的过程还需要将这个集合链上的所有的节点都打平
		 * 就是这条链的集合上的所有的节点都指向代表节点
		 * @param node
		 * @return
		 */
		// 这个方法是一个递归行为
		public Data findRepresent(Data node) {
			Data father = fatherMap.get(node);
			if(father != node) {
				father = findRepresent(father);
			}
			fatherMap.put(node, father);  // 这一步就是打平的过程  将节点的父节点指向返回的代表节点
			return father;  // 把代表节点传递给子过程
		}
		
		// 查找两个节点是否是属于同一个集合
		public boolean isSameSet(Data a, Data b) {
			return findRepresent(a) == findRepresent(b);
		}
		
		// 两个节点对应的集合进行合并
		public void union(Data a, Data b) {
			if(a == null || b == null) {
				return;
			}
			Data aHead = findRepresent(a);
			Data bHead = findRepresent(b);
			if(aHead != bHead) { // 不在一个集合里面  才会去合并
				int aSetSize = sizeMap.get(aHead);  // 拿代表节点的size 就是这个集合的size  是有效的值
				int bSetSize = sizeMap.get(bHead);  // 
				if(aSetSize <= bSetSize) {
					fatherMap.put(aHead, bHead);  // 将 a 集合  挂在 b 集合 的下面
					sizeMap.put(bHead, aSetSize + bSetSize);  // 将集合的长度 重新放在合并之后的新的代表节点上
				} else {
					fatherMap.put(bHead, aHead);
					sizeMap.put(aHead, aSetSize + bSetSize);
				}
			}
		}
	}
}