介绍并查集文章 https://blog.csdn.net/zjy_code/article/details/80634149

    image.png

    1. public class UnionFind {
    3.     public static class Element<V> {
    4.         public V value;
    6.         public Element(V value) {
    7.             this.value = value;
    8.         }
    10.     }
    12.     public static class UnionFindSet<V> {
    13.         public HashMap<V, Element<V>> elementMap;
    14.         // key 某个元素 value 该元素的父
    15.         public HashMap<Element<V>, Element<V>> fatherMap;
    16.         // key 某个集合的代表元素 value 该集合的大小
    17.         public HashMap<Element<V>, Integer> rankMap;
    19.         public UnionFindSet(List<V> list) {
    20.             elementMap = new HashMap<>();
    21.             fatherMap = new HashMap<>();
    22.             rankMap = new HashMap<>();
    23.             for (V value : list) {
    24.                 Element<V> element = new Element<V>(value);
    25.                 elementMap.put(value, element);
    26.                 fatherMap.put(element, element);
    27.                 rankMap.put(element, 1);
    28.             }
    29.         }
    31.         private Element<V> findHead(Element<V> element) {
    32.             Stack<Element<V>> path = new Stack<>();
    33.             while (element != fatherMap.get(element)) {
    34.                 path.push(element);
    35.                 element = fatherMap.get(element);
    36.             }
    37.             while (!path.isEmpty()) {
    38.                 fatherMap.put(path.pop(), element);
    39.             }
    40.             return element;
    41.         }
    43.         public boolean isSameSet(V a, V b) {
    44.             if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
    45.                 return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
    46.             }
    47.             return false;
    48.         }
    50.         public void union(V a, V b) {
    51.             if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
    52.                 Element<V> aF = findHead(elementMap.get(a));
    53.                 Element<V> bF = findHead(elementMap.get(b));
    54.                 if (aF != bF) {
    55.                     Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
    56.                     Element<V> small = big == aF ? bF : aF;
    57.                     fatherMap.put(small, big);
    58.                     rankMap.put(big, rankMap.get(aF) + rankMap.get(bF));
    59.                     rankMap.remove(small);
    60.                 }
    61.             }
    62.         }
    63.     }
    64. }