定义

其实并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。

并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作：

查询元素a和元素b是否属于同一组
合并元素a和元素b所在组

并查集的结构

用数组表达的树表示

例子

set s= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

pairs of equivalence:(0 4),(3 1),(6 10),(8 9),(7 4),(6 8),(3 5),(2 11)，(11 0)

Initial:{0}，{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}，{9}, {10}，{11}

union(0,4): {0，4}，{1}，{2}，{3}，{5}，{6}，{7}，{8}，{9}, {10}，{11}

union(3,1): {0，4}，{1，3}，{2}，{5}，{6}，{7}，{8}，{9}，{10}, {11}

基本功能

并查集通常有两个基本操作，find与union

public class DisjSets{
    public DisjSets( int numElements )
        public void union( int root1, int root2 );
        public int find( int x )
        private int[] parent;
}

find(x)

dset_1
find(7)=find(8)=find(9)=find(1)=1
find(2)=find(10)=find(5)=5

union(i, j)

diset_2

一些问题和改进

dset_3

如果可能出现很差的情况，增加复杂度

improve Union two rules:

Weight rule: if the number of nodes in tree i is less than the number in tree j, then make j the parent of i; otherwise,make i the parent of j.
Height rule: if the height of tree i is less than that of tree j, then make j the parent of i; otherwise,make i the parent of j.

Weight Rule

Besides the *parent* field, each node has *a boolean field root* .The root field is true iff the node is presently a root node. The parent field of each root node is used to keep a count of the total number of nodes in the tree.

![dset_4](D:MyBlogsourceimagesdset_4.jpg)

```java
public DisjointSet(int size, RuleType ruleType) {
        parant = new int[size + 1];
        root = new boolean[size + 1];
        for (int i = 1; i < size + 1; i++) {
            root[i] = true;
            parant[i] = 1;
        }
        rule = ruleType;
    }

    public int find(int e) {
        while (!root[e])
            e = parant[e];
        break;
        return e;
    }

    public void union(int i, int j) {
        unionRoot(find(i), find(j));
    }

    private void unionRoot(int root1, int root2) {
        if (parant[root1] < parant[root2]) { // root1 become subtree of root2
            parant[root2] += parant[root1];
            root[root1] = false;
            parant[root1] = root2;
        } else {
            parant[root1] += parant[root2];
            root[root2] = false;
            parant[root2] = root1;
        }
    }
```

Height Rule

用一个数组来实现，根结点中放负数，而且是代表高度。

![dset_5](D:MyBlogsourceimagesdset_5.jpg)

![dset_6](D:MyBlogsourceimagesdset_6.jpg)

```java
public DisjointSet(int size, RuleType ruleType) {
        parant = new int[size + 1];
        for (int i = 1; i < size + 1; i++) {
            parant[i] = -1;
        }
        rule = ruleType;
    }

    public int find(int e) {
        while (parant[e] > 0)
        	e = parant[e];
        break;
        return e;
    }

    public void union(int i, int j) {
        unionRoot(find(i), find(j));
    }

    private void unionRoot(int root1, int root2) {
        if (parant[root1] < parant[root2]) { 
            // height 1 > height 2, 2 become subtree of 1
            parant[root2] = root1;
        } else if (parant[root1] > parant[root2]) {
        	parant[root1] = root2;
        } else { // same height
        	parant[root1] = root2;
            root2--;
        }
    }
```

完整实现代码

public class DisjointSet {
    public static void main(String[] args) {
        DisjointSet disjointSet = new DisjointSet(10,RuleType.WEIGHT_RULE);
        disjointSet.union(1,2);
        disjointSet.union(2,3);
        disjointSet.union(4,5);
        disjointSet.union(5,6);
        disjointSet.union(6,7);
        disjointSet.union(2,5);
        disjointSet.print();
        System.out.println(disjointSet.find(2));
    }
    public enum RuleType {
        WEIGHT_RULE, HEIGHT_RULE
    }

    private RuleType rule;
    private int[] parant;
    private boolean[] root; // 用于WeightRule

    public DisjointSet(int size) {
        this(size, RuleType.HEIGHT_RULE); // 默认使用HeightRule
    }

    public DisjointSet(int size, RuleType ruleType) {
        parant = new int[size + 1];
        if (ruleType == RuleType.WEIGHT_RULE) {
            root = new boolean[size + 1];
            for (int i = 1; i < size + 1; i++) {
                root[i] = true;
                parant[i] = 1;
            }
        } else if (ruleType == RuleType.HEIGHT_RULE) {
            for (int i = 1; i < size + 1; i++) {
                parant[i] = -1;
            }
        }
        rule = ruleType;
    }

    public int find(int e) {
        switch (rule) {
            case HEIGHT_RULE:
                while (parant[e] > 0)
                    e = parant[e];
                break;
            case WEIGHT_RULE:
                while (!root[e])
                    e = parant[e];
                break;
        }
        return e;
    }

    public void union(int i, int j) {
        unionRoot(find(i), find(j));
    }

    private void unionRoot(int root1, int root2) {
        switch (rule) {
            case HEIGHT_RULE:
                if (parant[root1] < parant[root2]) { 
                    // height 1 > height 2, 2 become subtree of 1
                    parant[root2] = root1;
                } else if (parant[root1] > parant[root2]) {
                    parant[root1] = root2;
                } else { // same height
                    parant[root1] = root2;
                    root2--;
                }
                break;
            case WEIGHT_RULE:
                if (parant[root1] < parant[root2]) { 
                    // root1 become subtree of root2
                    parant[root2] += parant[root1];
                    root[root1] = false;
                    parant[root1] = root2;
                } else {
                    parant[root1] += parant[root2];
                    root[root2] = false;
                    parant[root2] = root1;
                }
                break;
        }
    }

    public void print(){
        for (int i = 1; i <parant.length ; i++) {
            if ((rule == RuleType.HEIGHT_RULE &&parant[i]<0)||(rule==RuleType.WEIGHT_RULE&&root[i])){
                System.out.println("|-----"+i);
                print(i,1);
            }
        }
    }
    private void print(int father,int blank){
        for (int i = 1; i < parant.length; i++) {
            if((rule==RuleType.HEIGHT_RULE&&parant[i]==father)||(rule==RuleType.WEIGHT_RULE&&parant[i]==father&&(!root[i]))){
                for (int j = 0; j < blank; j++) {
                    System.out.print("  ");
                }
                System.out.println("|-----"+i);
                print(i,blank+1);
            }
        }
    }
}