并查集快速查找

并查集快速查找

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。

查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。

...

private int find(int p) {

    assert p >= 0 && p < count;

    return id[p];

}

...

合并元素 p 和元素 q 所属的集合， 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并，这个过程是 O(n) 复杂度。

...

public void unionElements(int p, int q) {

    int pID = find(p);

    int qID = find(q);

    if (pID == qID)

        return;

    for (int i = 0; i < count; i++)

        if (id[i] == pID)

            id[i] = qID;

}

...

Java 实例代码

源码包下载：Download

UnionFind1.java 文件代码：

package zhishitu.union;



/**

 * 第一版union-Find

 */

public class UnionFind1 {

    // 我们的第一版Union-Find本质就是一个数组

    private int[] id;

    // 数据个数

    private int count;



    public UnionFind1(int n) {

        count = n;

        id = new int[n];

        // 初始化, 每一个id[i]指向自己, 没有合并的元素

        for (int i = 0; i < n; i++)

            id[i] = i;

    }



    // 查找过程, 查找元素p所对应的集合编号

    private int find(int p) {

        assert p >= 0 && p < count;

        return id[p];

    }



    // 查看元素p和元素q是否所属一个集合

    // O(1)复杂度

    public boolean isConnected(int p, int q) {

        return find(p) == find(q);

    }



    // 合并元素p和元素q所属的集合

    // O(n) 复杂度

    public void unionElements(int p, int q) {



        int pID = find(p);

        int qID = find(q);



        if (pID == qID)

            return;



        // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并

        for (int i = 0; i < count; i++)

            if (id[i] == pID)

                id[i] = qID;

    }

}