Union Find

问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数 p, q 可以被理解为“p 和 q 是相连的”。我们假设“相连”是一种等价关系，这也就意味着它具有：

自反性
对称性
传递性

class UF:

class UF {
private:
    int *id_, count_, length_; // 分量id，分量数量，触点个数

public:
    UF(int N);
    void Union(int p, int q);
    int Find(int p);
    bool Connected(int p, int q);

    int count();
    int length();

    ~UF();
};

main function:

int main() {
    // ...
    UF uf = UF(N);
    for (int i = 0; i < p.size(); ++i) {
        if (uf.Connected(p[i], q[i]))
            continue;
        uf.Union(p[i], q[i]);
        printf("%d %d", p[i], q[i]);
    }
    printf("%d components", uf.count());
    return 0;
}

Quick Find

利用传递性，若 4 与 3 相连，3 又与 8 相连，那么 4 一定与 8 相连。

void UF::Union(int p, int q) {
    int p_id = Find(p); // 1
    int q_id = Find(q); // 1

    if (p_id == q_id) return;

    for (int i = 0; i < length_; ++i) {
        if (id_[i] == p_id) // N
            id_[i] = q_id;  // 1 ~ (N - 1)
    }
    --count_;
}

int UF::Find(int p) {
    return id_[p];
}

分析

对于每一对输入，~Union()~ 都需要扫描整个 id_ 数组。

每次 find() 调用只需访问数组一次，而归并两个分量的 Union() 操作访问数组的次数在 (N+3) 到 (2N+1) 之间。

时间复杂度： \[T(n)=(n-1)(2n+1)\sim O(n^2)\]

Quick Union

利用树来表示触点间的关系。

void UF::Union(int p, int q) {
    int p_root = Find(p);
    int q_root = Find(q);
    if (p_root == q_root)
        return;
    id_[p_root] = q_root;
    --count_;
}

int UF::Find(int p) {
    while (p != id_[p])
        p = id_[p];
    return p;
}

分析

Find() 方法访问数组的次数为 1 加上给定触点所对应的节点的深度的两倍。 Union() 和 Connected() 访问数组的次数为两次 Find() 操作（如果 Union 中给定的两个触点分别存在于不同的树中则还需要加 1）。

对于输入队列 0-1, 0-2, 0-3… 等， union() 访问数组的次数为 \(2i+1\)。

时间复杂度： \[T(n)=3+5+7+\cdots+(2n-1)\sim O(n^2)\]

Weighted Union Find

class UF {
private:
    int *id_, *sz_, count_; // 父节点数组，各个根节点所对应的分量的大小，分量数量

public:
    UF(int N);
    void Union(int p, int q);
    int Find(int p);
    bool Connected(int p, int q);

    int count();

    ~UF();
};

UF::UF(int N) {
    count_ = N;
    id_ = new int[N];
    for (int i = 0; i < N; ++i) {
        id_[i] = i;
    }
    sz_ = new int[N];
    for (int i = 0; i < N; ++i) {
        sz_[i] = 1;
    }
}

int UF::count() {
    return count_;
}

bool UF::Connected(int p, int q) {
    return Find(p) == Find(q);
}

UF::~UF() {
    delete[] id_;
    delete[] sz_;
}

void UF::Union(int p, int q) {
    int p_root = Find(p);
    int q_root = Find(q);
    if (p_root == q_root)
        return;
    if (sz_[p_root] < sz_[q_root]) {
        id_[p_root]  = q_root;
        sz_[q_root] += sz_[p_root];
    } else {
        id_[q_root]  = p_root;
        sz_[p_root] += sz_[q_root];
    }
    --count_;
}

int UF::Find(int p) {
    while (p != id_[p])
        p = id_[p];
    return p;
}

分析

对于 N 个触点，加权 quick union 算法构造的森林中的任意节点的深度最多为 \(\lg N\)。

证明: 森林中大小为 \(k\) 的树高度最多为 \(\lg k\)。当 \(k = 1\) 时，\(D = 0\) 根据归纳法，我们假设大小为 \(i\) 的树的高度最多为 \(\lg i\)，其中 \(i < k\)。设 \(i \le j\) 且 \(i + j = k\) 当我们将大小为 \(i\) 和大小为 \(j\) 的树归并时，quick union 算法会使小树中所有节点的深度增加 1，但它们所在的树的大小为 \(i + j = k\)，而 \(1 + \lg i = \lg(i+i) \le \lg(i+j) = \lg k\)，性质成立。

时间复杂度： \[T(n)=\lg n + \lg n \sim O(\lg N)\]

cell-probe 模型：一种计算模型，我们只会记录对随机内存的访问，内存大小足以保存所有输入且假设其他操作均没有成本。