并查集的实现

题目描述：

给定一个没有重复值的整型数组arr，初始时认为arr中每一个数各自都是一个单独的集合，请设计一种叫UnionFind的结构，并提供以下两个操作。

（1）boolean isSameSet(int a,int b)：查询a和b这两个数是否属于一个集合。

（2）void union(int a,int b)：把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合。

要求：

如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单词调用isSameSet或union方法的平均时间复杂度为O(1)。

解答：

符合题目功能要求的结构就是并查集。

 1 class Element<V> {
 2     public V value;
 3     public Element(V value) {
 4         this.value=value;
 5     }
 6 }
 7 public class UnionFindSet<V> {
 8     public HashMap<V,Element<V>> elementMap;
 9     public HashMap<Element<V>,Element<V>> fatherMap;
10     public HashMap<Element<V>,Integer> rankMap;
11 
12     public UnionFindSet(List<V> list) {
13         elementMap=new HashMap<>();
14         fatherMap =new HashMap<>();
15         rankMap=new HashMap<>();
16         for (V value : list) {
17             Element<V> element=new Element<V>(value);
18             elementMap.put(value,element);
19             fatherMap.put(element,element);
20             rankMap.put(element,1);
21             
22         }
23     }
24     private Element<V> findHead(Element<V> element) {
25         Stack<Element<V>> path=new Stack<>();
26         while(element!=fatherMap.get(element)) {
27             path.push(element);
28             element=fatherMap.get(element);
29         }
30         while (!path.isEmpty()) {
31             fatherMap.put(path.pop(),element);
32         }
33         return element;
34     }
35 
36     public boolean isSameSet(V a,V b) {
37         if (elementMap.containsKey(a)&&elementMap.containsKey(b)) {
38             return findHead(elementMap.get(a))==findHead(elementMap.get(b));
39         }
40         return false;
41     }
42     public void union(V a,V b) {
43         if (elementMap.containsKey(a)&&elementMap.containsKey(b)) {
44             Element<V> aF=findHead(elementMap.get(a));
45             Element<V> bF=findHead(elementMap.get(b));
46             if (aF!=bF) {
47                 Element<V> big=rankMap.get(aF)>rankMap.get(bF)?aF:bF;
48                 Element<V> small=big==aF?bF:aF;
49                 fatherMap.put(small,big);
50                 rankMap.put(big,rankMap.get(aF)+rankMap.get(bF));
51                 rankMap.remove(small);
52             }
53         }
54     }
55 }

欢迎评论，共同进步！！