Union Find

Union Find data structure 又稱 disjoint set data structure。它是一個資料結構，用來儲存一堆 disjoint set。它提供兩個操作，一個是用來合併兩個 sets，另一個是用來尋找給定元素的 set。

Union Find

Union Find data structure 中有一個叫 parents 的 array。它記錄著每一個元素歸屬的 set。一開始，每個元素自成一個 set。之後，透過呼叫 union() 來合併給定的兩個 sets。find() 回傳傳入元素的 set 編號。

public class UnionFind {
    private final int[] parents;

    public UnionFind(int size) {
        parents = new int[size];
        for (int i = 0; i < size; i++) {
            parents[i] = i;
        }
    }

    int find(int x) {
        while (x != parents[x]) {
            parents[x] = parents[parents[x]];
            x = parents[x];
        }
        return x;
    }

    void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);

        if (parentX < parentY) {
            parents[parentY] = parentX;
        } else if (parentX > parentY) {
            parents[parentX] = parentY;
        }
    }
}

時間與空間複雜度

在一開始初始化 parents 時，需要的時間複雜度為 O(n)，其中 n 為元素數量。

Find() 需要的時間複雜度為 O(α(n))，其中 α 是 inverse Ackermann function，它會成長非常地慢，所以可以將它視為常數時間。所以，O(α(n)) ≈ O(1)。因此，Find() 的時間複雜度為 O(1)。

Union() 使用到 Find()，所以它的時間複雜度是 O(1)。

Union Find data structure 內部需要一個 parents。所以，它的空間複雜度為 O(n)。

範例

參考

• Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithm.
• Disjoint-set data structure, Wikipedia.