\(9.2\)快速查找

1.并查集的构造

  直观上，我们可以通过\(ListOfSet\)来表示并查集，例如[{0}, {1}, {2}, {3}, {4}, {5}, {6}]。但是，这种形式的并查集难以合并。

  我们考虑只用一个数组来实现并查集的合并操作，该数组按如下方式构造：

• 数组的下标值代表元素本身。
• 数组下标对应的值代表元素所属集合的序号。

  例如，我们可以如下表示{0, 1, 2, 4}, {3, 5}, {6}：

  集合的序号并不重要，只需要确保相同的集合的值相同即可。

2.connect操作

  有了上面的构造，我们可以通过更改数组对应下标的值来实现合并。例如，假如我们想将\(2\)与\(3\)合并：

3.isConnected操作

  为了检查isConnected(x, y)，我们只需要检查它们对应集合的序号是否相等即可。这只需要常数时间。

4.总结与代码实现

public class QuickFindDS implements DisjointSets {
    private int[] id;

    public QuickFindDS(int N) {
        id = new int[N];
        // initialize the parent
        for (int i = 0; i < N; i += 1) {
            id[i] = i;
        }
    }

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

    public boolean isConnected(int p, int q) {
        return id[p] == id[q];
    }
}