算法初阶笔记——并查集

1.概念
并查集（Union Find）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
功能：a查找两个元素是否属于同一个集合:isSameSet(A,B) A所在的集合为Set1，B所在的集合为Set2，则返回Set1和Set2是否属于同一个集合；b将两个元素各自所在的集合合并到一起

isSameSet(A,B)

合并两个集合。

唯一优化

例如：1,2,3,4,5合并后的集合为下图中间所示，问2,5是否在同一个集合中，2,5分别往上找到代表节点3，则说明在同一个集合。然后2,5,指向3节点的链中的节点全部扁平，指向3节点，2,5下面还有节点则保持不动


2.主要操作
（1）初始化
把每个点所在集合初始化为其自身。通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。
（2）查找
查找元素所在的集合，即根节点。
（3）合并
将两个元素所在的集合合并为一个集合。通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

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

public class UnionFind {
    public static class Node{
        //whataver you like
    }
    public static class unionFindSet{
        public HashMap<Node, Node> fatherMap;
        public HashMap<Node, Integer> sizeMap;
        public unionFindSet(List<Node> nodes){
            makeSets(nodes);
        }
        private void makeSets(List<Node> nodes){
            fatherMap = new HashMap<Node, Node>();
            sizeMap = new HashMap<Node, Integer>();
            for(Node node : nodes){
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        private Node findHead(Node node){   //找到代表节点,并扁平优化集合结构
            Stack<Node> stack = new Stack<>();
            Node curr = node;
            Node parent = fatherMap.get(curr);
            while(curr != parent){
                stack.push(node);
                curr = parent;
                parent = fatherMap.get(curr);
            }
            while (!stack.isEmpty()){
                fatherMap.put(stack.pop(), parent);
            }
            return parent;
        }
        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);
                }
            }
        }
    }
}