并查集

Dynamic Connectivity

动态连通性问题，满足：

1.symmetric：自反性

2.transitive:传递性

3.reflexive：对称性

API

QuickFind

 

public class QuickFind {
    private int[] id;
    public QuickFind(int nums){
        id = new int[nums];
        for(int i = 0; i < id.length ; i++){
            id[i] = i;
        }
    }
    public boolean isConnected(int p , int q ){
        return (id[p] == id[q]);
    }

    public void union(int p , int q ){
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++) {
            if(id[i] == pid){
                id[i] = qid;
            }
        }
    }

}

 

刚开始每个元素都与自己连通，进行union(p,q) == 将p 连接到 q上，quickfind将pid全部改为qid。

QuickUnion

public class QuickUnionUF {
    private int[] id;
    public QuickUnionUF(int num){
        id = new int[num];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }
    public int findroot(int i){
        while(id[i] != i){
            i = id[i];
        }
        return i;
    }
    public boolean isConnected(int p , int q){
      return findroot(p) == findroot(q);
    }
    public void union(int p , int q ){
        int proot = findroot(p);
        int qroot = findroot(q);
        id[proot] = qroot;
    }

}

QuickUnion将连通分量抽象成树，用根节点是否一致来判断连通性；

缺陷：数的高度很高，查找根节点操作需要进行多次，速度不快。

Weighted QuickUnion

 1 public class WeightedQuickUnionUF {
 2     private int[] parents;
 3     private int count;
 4     private int[] size;
 5     public WeightedQuickUnionUF(int num){
 6         parents = new int[num];
 7         size = new int[num];
 8         count = num;
 9         for (int i = 0; i < num; i++) {
10             parents[i] = i;
11             size[i] = 1;
12         }
13     }
14     public int find(int p ){
15         while(parents[p] != p){
16             parents[p] = parents[parents[p]];   //路径压缩!!!!
17             p = parents[p];
18         }
19         return p;
20     }
21     public boolean isConnected(int p , int q ){
22         return (parents[p] == parents[q]);
23     }
24     public void union(int p , int q ){
25         if(isConnected(p,q)){
26             return;
27         }else{
28             int pid = find(p);
29             int qid = find(q);
30             if(size[p] <= size[q]){
31                 parents[p] = qid;
32                 size[qid] += size[pid];
33             }else{
34                 parents[q] = pid;
35                 size[pid] += size[qid];
36             }
37             count--;
38         }
39     }
40 }

优点：任意节点x的深度最多为lgN，原因是只有向size更大的节点合并时，树的高度才会+1，因此总共N个节点，最多可以加倍lgN次，高度最高为lgN