并查集:

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。(来自百度百科)

关于并查集的实现,有两种思路.
一种是基于数组 ,这种思路是将每个元素所属的集合编号存在数组中,然后随着集合编号的合并和,修改数组的编号即可,代码实现如下

首先定义一个并查集的接口:

/** * @author BestQiang */
public interface UF {
    int getSize();
    boolean isConnected(int p, int q);
    void unionELements(int p, int q);
}

接下来实现并查集接口:

/** * @author BestQiang */
public class UnionFind1 implements UF {

    private int[] id;

    public UnionFind1(int size) {
        // 初始化并查集,此时所有元素属于不同的集合
        this.id = new int[size];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    @Override
    public int getSize() {
        return 0;
    }

    /** * 查找元素p所对应的的集合编号 * @param p * @return */
    private int find(int p) {
        if(p < 0 && p >= id.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        // 直接返回对应的集合编号即可
        return id[p];
    }

    /** * 查看元素p和元素q是否所属一个集合 * @param p * @param q * @return */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /** * 合并元素p和元素q所属的集合 * @param p * @param q */
    @Override
    public void unionELements(int p, int q) {
        // 首先判断是否同属一个集合,如果属于一个集合,直接结束即可,因为不需要合并
        int pID = find(p);
        int qID = find(q);
        if(pID == qID) {
            return;
        }
        
        // 循环宾利数组,将原来属于一个集合的元素的所属集合修改为新的集合
        for (int i = 0; i < id.length; i++) {
            if(id[i] == pID) {
                id[i] = qID;
            }
        }
    }

}

另一种是基于树 ,这种树不是一般的树,这种树是由下层节点指向上层节点的树,基于数组实现,如图所示:

将数组的值储存为父节点的id即可,代码实现如下:

/** * @author BestQiang */
public class UnionFind2 implements UF{
    private int[] parent;
    public UnionFind2(int size) {
        parent = new int[size];
        for(int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /** * 查找过程,查找元素p所对应的集合编号 * O(h)复杂度,h为树的高度 * @param p * @return */
    private int find(int p) {
        if(p < 0 && p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound");
        }

        // 循环查找p的根节点(原理是查找p的上层节点,找到后将上层节点赋值给p,继续找上层节点,相同才截止)
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    /** * 查看元素p和元素q是否所属一个集合 * O(h)复杂度, h为树的高度 * @param p * @param q * @return */
    @Override
    public boolean isConnected(int p, int q) {
        // 如果根节点相同,直接判定为所属一个集合
        return find(p) == find(q);
    }

    /** * 合并两个节点 * @param p * @param q */
    @Override
    public void unionELements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        // 根节点相同,代表已经所属同组,直接结束即可
        if(pRoot == qRoot) {
            return;
        }

        // 根节点不同,就将pRoot的上层设置到q的根节点即可
        // 为什么要直接连接到qRoot的根节点,不直接连接到qRoot的上层节点?目的是发挥树的特性,便于查询
        parent[pRoot] = qRoot;
    }
}