并查集结构

package com.harrison.class10;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code01_UnionFind {
  // 自定义V类型，每个样本value外面包裹一层
  public static class Node<V>{
    V value;
    public Node(V v) {
      value=v;
    }
  }
  public static class UnionSet<V>{
    // 在nodes表里面，任何一个样本value都一一对应一个结点
    // 且初始化以后，永远不会有改动，只是记下对应关系
    public HashMap<V, Node<V>> nodes;
    // 每一个结点和自己的父结点都一一对应，记录在parents表里面
    public HashMap<Node<V>, Node<V>> parents;
    // 只有一个点，且这个点是集合的代表点
    public HashMap<Node<V>, Integer> sizeMap;
    public UnionSet(List<V> values) {// 用户把所有样本一次性给出
      for(V cur:values) {
        // 将每一个样本value都在外面包裹一层形成node
        Node<V> node=new Node<>(cur);
        // 记下对应关系，之后永不改变
        nodes.put(cur, node);
        // 因为一开始每一个样本只有自己，所以父结点仍然是自己
        parents.put(node, node);
        // 因为一开始每一个点都是代表点，所以集合大小就是1
        sizeMap.put(node, 1);
      }
    }
    // 从点cur开始，一直往上找，找到不能再往上的代表点，返回
    // 沿途所有结点都放入一个容器里（容器可以不是栈），目的是记下沿途路径
    public Node<V> findFather(Node<V> cur){
      Stack<Node<V>> path=new Stack<>();
      while(cur!=parents.get(cur)) {
        path.push(cur);
        cur=parents.get(cur);
      }
      // 跳出上面的循环后,cur一定指向代表点
      // 返回代表点之前，把沿途所有结点的父结点都改成代表点
      // 重要优化就体现在这，将链扁平化
      while(!path.isEmpty()) {
        parents.put(path.pop(), cur);
      }
      return cur;
    }
    public boolean isSameSet(V a,V b) {
      // 如果两个样本中有任何一个样本没有在nodes表里初始化，
      // 就必然不会在同一个集合里
      if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
        return false;
      }
      // if没中，说明两个样本都在nodes表里登记了
      // 通过样本找它所在集合的代表点，如果两个代表点的内存地址一样
      // 就说明是在同一个集合
      return findFather(nodes.get(a))==findFather(nodes.get(b));
    }
    // 注意：是a样本所在的整个集合 和 b样本所在的整个集合 进行合并
    public void union(V a,V b) {
      // 没有登记，无法合并
      if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
        return ;
      }
      // 登记了的话，找到自己所在集合的代表点
      Node<V> aHead=findFather(nodes.get(a));
      Node<V> bHead=findFather(nodes.get(b));
      // 只有两个代表点内存地址不一样才需要合并
      // 否则，说明这两个代表点所代表的两个集合本来就合并好了
      if(aHead!=bHead) {
        // 分别求得两个集合的的大小
        int aSetSize=sizeMap.get(aHead);
        int bSetSize=sizeMap.get(bHead);
        Node<V> big=aSetSize>=bSetSize?aHead:bHead;
        Node<V> small=big==aHead?bHead:aHead;
        // 小集合挂在大集合的下面
        // 直接把小集合头节点的父结点改为大集合的头节点
        parents.put(small, big);
        // 所以大集合的大小就变为两个集合大小相加
        sizeMap.put(big, aSetSize+bSetSize);
        // 小集合头节点不在作为代表点了，所以删掉在sizeMap里的记录
        sizeMap.remove(small);
      }
    }
  }
}