算法-并查集-1

 1 public class Element<V> {
 2     public V value;
 3 
 4     public Element(V value) {
 5         this.value = value;
 6     }
 7 
 8     public static class UnionFindSet<V> {
 9         public Map<V, Element<V>> elementMap;
10         public Map<Element<V>, Element<V>> fatherMap;
11         public Map<Element<V>, Integer> sizeMap;
12 
13         public UnionFindSet(List<V> list) {
14             elementMap = new HashMap<>();
15             fatherMap = new HashMap<>();
16             sizeMap = new HashMap<>();
17             if (list != null && !list.isEmpty()) {
18                 for (V v : list) {
19                     Element<V> vElement = new Element<>(v);
20                     elementMap.put(v, vElement);
21                     fatherMap.put(vElement, vElement);
22                     sizeMap.put(vElement, 1);
23                 }
24             }
25         }
26 
27         public Element<V> findHead(Element<V> element) {
28             Stack<Element<V>> stack = new Stack<>();
29             while (fatherMap.get(element) != element) {
30                 stack.push(element);
31                 element = fatherMap.get(element);
32             }
33             while (!stack.isEmpty()) {
34                 fatherMap.put(stack.pop(), element);
35             }
36             return element;
37         }
38 
39         public boolean isSameSet(V a, V b) {
40             if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
41                 Element<V> aHead = findHead(elementMap.get(a));
42                 Element<V> bHead = findHead(elementMap.get(b));
43                 if (aHead == bHead) {
44                     return true;
45                 }
46             }
47             return false;
48 
49         }
50 
51         public void union(V a, V b) {
52             if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
53                 Element<V> aElement = elementMap.get(a);
54                 Element<V> bElement = elementMap.get(b);
55                 Element<V> aHead = findHead(aElement);
56                 Element<V> bHead = findHead(bElement);
57                 Integer aSize = sizeMap.get(aElement);
58                 Integer bSize = sizeMap.get(bElement);
59                 Element<V> big =aSize > bSize ? aHead : bHead;
60                 Element<V> small = big == aHead ? bHead : aHead;
61                 fatherMap.put(small,big);
62                 sizeMap.put(big,aSize+bSize);
63                 sizeMap.remove(small);
64             }
65         }
66     }
67 }
并查集结构可以快速查询是否在同一个集合
快速集合合并