Skip to content

Latest commit

 

History

History
229 lines (164 loc) · 5.07 KB

6.union-find.md

File metadata and controls

229 lines (164 loc) · 5.07 KB

并查集-解决连通性问题（图论）

并查集并不像链表二叉树一样有比较固定的实现方式

他的几种算法更是实现起来多样

Quick—Find算法

  1. 基于染色的思想，一开始所有点的颜色不同
  2. 连接两个点的操作，可以看成將一种颜色的点染成另一种颜色
  3. 如果两个点颜色一样，证明联通，否则不联通
  4. 这种方法叫做并查集的： Quick-Find 算法

注意了，虽然上面是用点，但是实际上连接的是两个集合

有一个元素的集合也是集合！

class UnionSet {
public :
    int *color, n;
    // 用相同的颜色代表连通性
    UnionSet(int n) : n(n) {
        color = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            color[i] = i;
        }
    }
    int find(int x) { return color[x]; }
    // quick_find
    // find 通过下标即可访问 O(1)
    // 但是merge要遍历遍数组
    // 所以复杂度O(n)
    void merge(int a, int b) {
        if (color[a] == color[b]) return ;
        int cb = color[b];
        // 把b染成a的颜色
        for (int i = 0; i <= n; i++) {
            if (color[i] == cb) color[i] = color[a];
        }
        return ;
    }
};

Quick-Union算法

利用树形结构

联通合并操作都看树的深度！

子节点指向父节点，那么就和父节点一个颜色

image-20230320175801397

改进 按照节点数量进行Union

引入平均查找次数的概念

平均查找次数即为$\frac{总查找次数}{节点总数}$

那么是按照节点少的链接还是按照深度少的链接呢？

不妨设A树节点总数为sa，查找总次数为la

B树也一样

当将A接到B下面时，平均查找次数为：

$\frac{l_a + l_b + s_a}{s_a + s_b}$

当将B接到A下面时，平均查找次数为：

$\frac{l_a + l_b + s_b}{s_a + s_b}$

可见只和节点总数有关

Weighted-Quick-Union算法本质上就是在降低树高

如图，就是进行了树高的压缩

$find: log(n) \ merge: log(n)$

image-20230322105929253

class UnionSet {
public :
    int *father, *size, n;
    UnionSet(int n) : n(n) {
        size = new int[n + 1];
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }
    int find(int x) {
        if (father[x] == x) return x;
        return find(father[x]);
    }
    void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return ;
        // 把大的顶上去
        if (size[pa] < size[pb]) {
            father[pa] = pb;
            size[pb] += size[pa];
        } else {
            father[pb] = pa;
            size[pa] += size[pb];
        }
        return ;
    }
};

如果在进行一次路径的压缩

即在查找的时候，查到了不合理的路径

比如像链表一样的

就把它压缩成n叉树

这样find和merge的时间复杂度接近$O(1)$

这就是带权的路经压缩

#include <iostream>
#include <ios>
using namespace std;

class UnionSet {
public :
    int *father, *size, n;
    UnionSet(int n) : n(n) {
        size = new int[n + 1];
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }
    int find(int x) {
        if (father[x] == x) return x;
        // 你既然找了一遍x的父节点了
        // 何不把他存起来呢？
        int root = find(father[x]);
        father[x] = root;
        return root;
    }
    void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return ;
        // 把大的顶上去
        if (size[pa] < size[pb]) {
            father[pa] = pb;
            size[pb] += size[pa];
        } else {
            father[pb] = pa;
            size[pa] += size[pb];
        }
        return ;
    }
};


int main() {
    // 小知识
    // ios::sync_with_stdio(false);
    // 可以处理cin带来的速度慢的问题
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    UnionSet u(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        switch (a) {
            case 1: u.merge(b, c); break;
            case 2: if (u.find(b) == u.find(c)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

c++性能提升

但是其实日常用的最多的还是路径压缩

并不是带权

因为路经压缩只需要记录一下即可

编码的难度大大小于带权的

而且两者达到的优化程度差不多

总结

image-20230322155830994