并查集及经典问题

Quick-Find 算法

  • 联通判断 O(1)
  • 合并操作 O(n)
  1. // 染色法
  2. class UnionSet {
  3. public:
  4.     int *color, n;
  5.     UnionSet(int n) : n(n) {
  6.         color = new int[n + 1];
  7.         for (int i = 0; i <= n; ++i) {
  8.             color[i] = i;
  9.        }
  10.    }
  11.     int find(int x) {
  12.         return color[x];
  13.    }
  14.     void merge(int a, int b) {
  15.         int cb = color[b];
  16.         for (int i = 0; i <= n; ++i) {
  17.             if (color[i] == cb) {
  18.                 color[i] = color[a];
  19.            }
  20.        }
  21.         return;
  22.    }
  23. };

Quick-Union 算法

  • 联通判断 tree-height 树高

  • 合并操作 tree-height 树高

  • 优化

    • 树的高度
    • 节点数量
  1. // 将连通关系转换为树形结构，通过递归的方式快速判定
  2. class UnionSet {
  3. public:
  4.     int *boss, n;
  5.     UnionSet(int n) : n(n) {
  6.         boss = new int[n + 1];
  7.         for (int i = 0; i <= n; ++i) {
  8.             boss[i] = i;
  9.        }
  10.    }
  11.     int find(int x) {
  12.         if (boss[x] == x) { return x; }
  13.         return find(boss[x]);
  14.    }
  15.     void merge(int a, int b) {
  16.         int fa = find(a), fb = find(b);
  17.         if (fa == fb) { return; }
  18.         boss[fa] = fb;
  19.         return;
  20.    }
  21. };

Weighted-Quick-Union 算法

  • 判断节点数量
  • 通过考虑平均查找次数的方式，对合并过程进行优化
  1. // 通过考虑平均查找次数的方式，对合并过程进行优化。
  2. class UnionSet {
  3. public:
  4.     int *fa, *size, n;
  5.     UnionSet(int n) : n(n) {
  6.         fa = new int[n + 1];
  7.         size = new int[n + 1];
  8.         for (int i = 0; i <= n; ++i) {
  9.             fa[i] = i;
  10.             size[i] = 1;
  11.        }
  12.    }
  13.     int find(int x) {
  14.         if (fa[x] == x) { return x; }
  15.         return find(fa[x]);
  16.    }
  17.     void merge(int a, int b) {
  18.         int ra = find(a), rb = find(b);
  19.         if (ra == rb) { return; }
  20.         if (size[ra] < size[rb]) {
  21.             fa[ra] = rb;
  22.             size[rb] += size[ra];
  23.        } else {
  24.             fa[rb] = ra;
  25.             size[ra] += size[rb];
  26.        }
  27.         return;
  28.    }
  29. };

路径压缩 Weighted-Quick-Union 算法

  • 把所有节点挂到根节点上（扁平化管理）
  1. // 修改find操作
  2. class UnionSet {
  3. public :
  4.     int *fa, *size, n;
  5.     UnionSet(int n) : n(n) {
  6.         fa = new int[n + 1];
  7.         size = new int[n + 1];
  8.         for (int i = 0; i <= n; i++) {
  9.             fa[i] = i;
  10.             size[i] = 1;
  11.        }
  12.    }
  13.     int find(int x) {
  14.         if (fa[x] == x) { return x; }
  15.         int root = find(fa[x]);
  16.         fa[x] = root;
  17.         return root;
  18.    }
  19.     void merge(int a, int b) {
  20.         int ra = find(a), rb = find(b);
  21.         if (ra == rb) { return; }
  22.         if (size[ra] < size[rb]) {
  23.             fa[ra] = rb;
  24.             size[rb] += size[ra];
  25.        } else {
  26.             fa[rb] = ra;
  27.             size[ra] += size[rb];
  28.        }
  29.         return;
  30.    }
  31. };

带路径压缩的并查集模板

  1. class UnionFind {
  2.     constructor(n) {
  3.         this.boss = new Array(n).fill(0).map((val, ind) => ind);
  4.         this.size = new Array(n).fill(1);
  5.     }
  6.     get(x) {
  7.         return (this.boss[x] = this.boss[x] == x ? x : this.get(this.boss[x]));
  8.     }
  9.     merge(a, b) {
  10.         this.boss[this.get(a)] = this.get(b);
  11.     }
  12. }

并查集总结

并查集 (Union-Find) 及经典问题 - 图1