1.     并查集：支持两个集合合并，两个是否一个集合。让两个操作几乎都是O(1)<br />       如果使用链表 合并是O(1) 查询是否一个集合就不是了,使用hash表 查询是O(1)，合并就不是了。<br />使用往上值的图的方式：<br />        看两个是否一个集合：指针一直往上指，指到不能再指了,看是否同一个代表元素，是就是同一集合，否则不是。<br />        两个集合合并：当两个不是集合的情况都是自己指自己，改变某个顶指针，指向另外一个。 <br />                                 当两个是集合时候，数量少的顶部连向数量多的顶部。<br />        关键是往上指到不能再指了，这个过程如果链条过长会达到瓶颈，所以当指到不能再指的时候将沿途的节点都指向最上面的。
    1.     // 样本会进来包一层，叫做元素
    2.     public static class Node<V> {
    3.         V value;
    5.         public Node(V v) {
    6.             value = v;
    7.         }
    8.     }
    10.     // 并查集结构
    11.     public static class UnionFind<V> {
    12.         // 包一层 a对应a圈  
    13.         public HashMap<V, Node<V>> nodes;
    14.         // key 某个元素，value指该元素的父  。  小弟  大哥
    15.         public HashMap<Node<V>, Node<V>> parents;
    16.         // key 某个集合的代表元素  ，value 该集合的大小，包含一个顶点和有多少小弟
    17.         public HashMap<Node<V>, Integer> sizeMap;
    19.         public UnionFind(List<V> values) {
    20.             nodes = new HashMap<>();
    21.             parents = new HashMap<>();
    22.             sizeMap = new HashMap<>();
    23.             for (V cur : values) {
    24.                 Node<V> node = new Node<>(cur);// 包层圈
    25.                 nodes.put(cur, node); // 自己对应自己的圈
    26.                 parents.put(node, node); // 小弟 大哥 都是自己
    27.                 sizeMap.put(node, 1);// 自己是光杆大哥
    28.             }
    29.         }
    31.         // 给一个节点，往上到不能再往上，把顶点返回
    32.         public Node<V> findHead(Node<V> cur) {
    33.             Stack<Node<V>> path = new Stack<>();
    34.             // 不是顶点的时候
    35.             while (cur != parents.get(cur)) {
    36.                 // 沿途节点加入栈
    37.                 path.push(cur);
    38.                 // 获得最顶点
    39.                 cur = parents.get(cur);
    40.             }
    41.             while (!path.isEmpty()) {
    42.                 // 将这条链上的father全都改成cur，扁平化
    43.                 parents.put(path.pop(), cur);
    44.             }
    45.             return cur;
    46.         }
    48.         // 是否一个集合
    49.         public boolean isSameSet(V a, V b) {
    50.             // 是否初始化
    51.             if(nodes.containsKey(a)&& nodes.containsKey(b)){
    52.                 // 是不是同一个顶点
    53.                 return findHead(nodes.get(a)) == findHead(nodes.get(b));
    54.             }
    55.             return false;
    56.         }
    58.         // 合并
    59.         public void union(V a, V b) {
    60.             if(nodes.containsKey(a)&& nodes.containsKey(b)){
    61.                 // 找到各自顶点
    62.                 Node<V> aHead = findHead(nodes.get(a));
    63.                 Node<V> bHead = findHead(nodes.get(b));
    64.                 if (aHead != bHead) {
    65.                     int aSetSize = sizeMap.get(aHead);
    66.                     int bSetSize = sizeMap.get(bHead);
    67.                     // 设置数量多和数量少的集合顶点
    68.                     Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
    69.                     Node<V> small = big == aHead ? bHead : aHead;
    70.                     // 挂载
    71.                     parents.put(small, big);
    72.                     // 更改合并完大小
    73.                     sizeMap.put(big, aSetSize + bSetSize);
    74.                     // 删除之前的顶点，因为合并了。
    75.                     sizeMap.remove(small);
    76.                 }
    78.             }
    81.         }
    83.         public int sets() {
    84.             return sizeMap.size();
    85.         }
    87.     }