鸣谢

本文整理自 B 站视频 并查集，同时参考了如下文章：

在此对相关视频及文章作者表示深深的感谢。 由于本人才疏学浅，文章或存在不当之处，敬请阅读本文的读者批评指正。所有文章都会随着本人的认知水平和技能的提升进行及时更新。

并查简介

并查集是一种树形的数据结构，我们可以用它来解决一些具有联通关系的问题。可能你会问啥叫连通关系，咋不移动呢😅

我们举一个简单例子：
假如 a 和 b 是亲戚，b 和 c 是亲戚，那么可以得出 a 和 c 也是亲戚。某种情况下我们可以说这种串起来关系的就是联通。

在编程的时候，我们使用森林来表示这种连通性，使用数组实现这个森林。树的根节点唯一标识了一个集合，我们只要找到了某个

看下面这张图画了五个节点，各个节点都是独立的，互不相干。

Snip20220118_35.png

合并：把两个不相交的集合合并为一个集合。
查询：查询两个元素是否在同一个集合中。

并查集：合并、查找、集合

Quick Find

用一个数组表示整片森林，树的根节点唯一标识了一个集合。

只要找到了某个元素的树根，就能确定它在哪个集合里。

根节点的标志就是：父节点是其本身。

并查集的重要思想在于用集合中的一个元素代表集合。

下面我们对并查集的基本操作做个简单介绍。

初始化

把每个节点所在集合初始化为其自身。

  1. init() {
  2.     for (let i = 0; i < this.n; i++) this.father[i] = i;
  3. }

查找

Find：返回元素所在集合

  1. find(x) {
  2.   // 如果x的父节点是它自己， 那么x就是根节点
  3.   if(this.father[x] === x) return x;
  4.   // 否则，我们就继续向上查找
  5.   return this.find(this.father[x]);
  6. }

Query：查询两个元素是否在同一个集合中

  1. query(a, b) {
  2.   return this.find(a) === this.find(b);
  3. }

合并

将两个元素所在的集合合并为一个集合。

  1. merge(a, b) {
  2.   const fa = this.find(a);
  3.   const fb = this.find(b);
  4.   if(fa === fb) return;
  5.   this.father[fa] = fb;
  6. }

实现- Quick-Union

树状结构

用一个数组表示整片森林，树的根节点唯一标识了一个集合。

只要找到了某个元素的树根，就能确定它在哪个集合里。

根节点的标志就是：父节点是其本身。

并查集的重要思想在于用集合中的一个元素代表集合。

查询

查找元素所在的集合，即根节点

根节点的父节点为自己

要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

代码实现

  1. // 颜色即代表了集合的名字
  2. // quick-find算法
  3. class UnionSet1 {
  4.   constructor(n = 100) {
  5.     this.n = n;
  6.     this.color = new Array(n); // 集合的颜色
  7.     this.init();
  8.   }
  10.   // 将个节点的颜色定义为自身的颜色
  11.   init() {
  12.     for(let i = 0; i< this.n; i++) {
  13.       this.color[i] = i; // 集合的颜色初始化
  14.     }
  15.   }
  17.   // 查找x属于哪个集合
  18.   find(x) {
  19.     return this.color[x];
  20.   }
  22.   // 查询a，b是否属于同一个集合
  23.   query(a, b) {
  24.     return this.find(a) === this.find(b);
  25.   }
  27.   // 让 a 集合的节点颜色 涂 成 b集合的颜色
  28.   merge(a, b) {
  29.     const colorA = this.color[a];
  30.     for (let i = 0; i < this.n; i++) {
  31.       if(this.color[i] === colorA) { 
  32.         // 并不是只有color[a] 的颜色是color[a],
  33.         // 可能有好多颜色都是color[a]
  34.         this.color[i] = this.color[b];
  35.       }    
  36.     }
  37.   }
  38. }
  41. // queck-union 
  42. class UnionSet2 {
  43.   constructor(n = 100) {
  44.     this.n = n;
  45.     this.father = new Array(n);
  46.     this.init();
  47.   }
  49.   // 将个节点的父节点定义为自身
  50.   init() {
  51.     for(let i = 0; i< this.n; i++) {
  52.       this.father[i] = i; // 集合的父节点初始化
  53.     }
  54.   }
  56.   // 查找x属于哪个集合, x的根节点是谁
  57.   find(x) {
  58.     // 如果x的父节点是他自己， 那么x就是根节点
  59.     if(this.father[x] === x) return x;
  60.     // 否则，我们就继续向上查找
  61.     return this.find(this.father[x]);
  62.   }
  64.   // 查询a，b是否属于同一个集合
  65.   query(a, b) {
  66.     return this.find(a) === this.find(b);
  67.   }
  69.   // 
  70.   merge(a, b) {
  71.     const fa = this.find(a);
  72.     const fb = this.find(b);
  73.     if(fa === fb) return;
  74.     this.father[fa] = fb;
  75.   }
  76. }
  79. // weighted-queck-union // 优化find方法
  80. class UnionSet3 {
  81.   constructor(n = 100) {
  82.     this.n = n;
  83.     this.father = new Array(n);
  84.     this.size = new Array(n); // 存放当前集合的元素数量
  85.     this.init();
  86.   }
  89.   init() {
  90.     for(let i = 0; i< this.n; i++) {
  91.       this.father[i] = i; // 集合的父节点初始化
  92.       this.size[i] = 1;
  93.     }
  94.   }
  96.   find(x) {
  97.     // 如果x的父节点是他自己， 那么x就是根节点
  98.     if(this.father[x] === x) return x;
  99.     // 否则，我们就继续向上查找
  100.     return this.find(this.father[x]);
  101.   }
  103.   // 查询a，b是否属于同一个集合
  104.   query(a, b) {
  105.     return this.find(a) === this.find(b);
  106.   }
  108.   // 
  109.   merge(a, b) {
  110.     const fa = this.find(a);
  111.     const fb = this.find(b);
  112.     if(fa === fb) return;
  113.     if(this.size[fa] < this.size[fb]) {
  114.       this.father[fa] = fb; // 将a合并到b中
  115.       this.size[fb] += this.size[fa]; // b集合的元素数量要加上a集合的数量
  116.     } else {
  117.       this.father[fb] = fa; // 将a合并到b中
  118.       this.size[fa] += this.size[fb];
  119.     }
  120.   }
  121. }
  123. // /**带路径压缩的**/ weighted-queck-union
  124. class UnionSet4 {
  125.   constructor(n = 100) {
  126.     this.n = n;
  127.     this.father = new Array(n);
  128.     this.size = new Array(n); // 存放当前集合的元素数量
  129.     this.init();
  130.   }
  132.   init() {
  133.     for(let i = 0; i< this.n; i++) {
  134.       this.father[i] = i; // 集合的父节点初始化
  135.       this.size[i] = 1;
  136.     }
  137.   }
  139.   find(x) {
  140.     // 如果x的父节点是他自己， 那么x就是根节点
  141.     if(this.father[x] === x) return x;
  142.     // 否则，我们就继续向上查找
  143.     const root = this.find(this.father[x]);
  144.     ///***/// 将 x 直接挂到根节点上
  145.     this.father[x] = root;
  146.     return root;
  147.   }
  149.   // 查询a，b是否属于同一个集合
  150.   query(a, b) {
  151.     return this.find(a) === this.find(b);
  152.   }
  154.   // 
  155.   merge(a, b) {
  156.     const fa = this.find(a);
  157.     const fb = this.find(b);
  158.     if(fa === fb) return;
  159.     if(this.size[fa] < this.size[fb]) {
  160.       this.father[fa] = fb; // 将a合并到b中
  161.       this.size[fb] += this.size[fa]; // b集合的元素数量要加上a集合的数量
  162.     } else {
  163.       this.father[fb] = fa; // 将a合并到b中
  164.       this.size[fa] += this.size[fb];
  165.     }
  166.   }
  167. }
  170.  /**带路径压缩的**/
  171. class UnionSet {
  172.   constructor(n = 100) {
  173.     this.n = n;
  174.     this.father = new Array(n);
  175.     this.init()
  176.   }
  177.   init() {
  178.     for (let i = 0; i < this.n; i++) this.father[i] = i;
  179.   }
  181.   find(x) {
  182.     return this.father[x] = (this.father[x] === x ? x : this.find(this.father[x]));
  183.   }
  185.   merge(a, b) {
  186.     this.father[this.find(a)] = this.find(b);
  187.   }
  188.   query(a, b) {
  189.     return this.find(a) === this.find(b);
  190.   }
  191. }
  195. function test() {
  196.   const unionSet = new UnionSet(100);
  197.   unionSet.merge(3, 1);
  198.   unionSet.merge(1, 4); 
  199.   console.log(`1属于集合 ${unionSet.find(1)}`);
  200.   console.log(`4属于集合 ${unionSet.find(4)}`);
  201.   console.log(`6属于集合 ${unionSet.find(6)}`);
  202.   console.log(`3、4属于一个集合 ${unionSet.query(3, 4)}`);
  203.   console.log(`3、6属于一个集合 ${unionSet.query(3, 6)}`);
  204. }
  205. test();

优化-带路径压缩的Weighted-Quick-Union

  • 树结构中，树的具体结构并不重要
  • 扁平化管理

平均查找次数 = 总查找次数 / 总节点数

练习

547.省份数量

  1. 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
  3. 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
  5. 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
  7. 返回矩阵中 省份 的数量。
  11. 示例 1：
  14. 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
  15. 输出：2
  16. 示例 2：
  19. 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
  20. 输出：3
  23. 提示：
  25. 1 <= n <= 200
  26. n == isConnected.length
  27. n == isConnected[i].length
  28. isConnected[i][j] 为 1 或 0
  29. isConnected[i][i] == 1
  30. isConnected[i][j] == isConnected[j][i]
  32. 来源：力扣（LeetCode）
  33. 链接：https://leetcode-cn.com/problems/number-of-provinces
  34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class UnionFind {
    constructor(size) {
        this.parent = [];
        this.count = 0;
        for (let i = 0; i < size; i++) {
            this.parent[i] = i;
            this.count++;
        }
    }
    find(p) {
        if (p != this.parent[p]) this.parent[p] = this.find(this.parent[p]);
        return this.parent[p];
    }
    getCount() {
        return this.count;
    }
    isConnected(p, q) {
        return this.find(p) == this.find(q);
    }
    union(p, q) {
        const pRoot = this.find(p);
        const qRoot = this.find(q);

        if (pRoot == qRoot) return;

        this.parent[pRoot] = qRoot;
        this.count--;
    }
}

function findCircleNum(isConnected) {
    const len = isConnected.length;
    const uf = new UnionFind(len);
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (isConnected[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    return uf.getCount();
}

200.岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。



示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3


提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

let count = 0;
class UnionSet {
  constructor(n = 100) {
    this.n = n;
    this.father = new Array(n);
    this.init(n);
  }
  init(n) {
    for (let i = 0; i < n; i++) this.father[i] = i;
  }

  find(x) {
    return this.father[x] = ((this.father[x] == x ? x : this.find(this.father[x])));
  }
  merge(a, b) {
    const fa = this.find(a); 
    const fb = this.find(b); 
    if(fa === fb) return false;

    this.father[fa] = fb;
    return true;
  }
}

var numIslands = function(grid) {
  let row = grid.length;
  let col = grid[0].length;
  const u = new UnionSet(row * col);
  let count = 0;

  for (let i = 0; i < row; i++) { 
    for (let j = 0; j < col; j++) { 
      if (grid[i][j] == '0') continue;
      count++;

      if (j + 1 < col && grid[i] [j + 1] == '1') { // 右
        u.merge(i * col + j, i * col + j + 1) && count--; 
      } 
      if (i + 1 < row && grid[i + 1] [j] == '1') { // 下
        u.merge(i * col + j, (i + 1) * col + j) && count--; 
      }
    }
  }

  return count;
};

990.等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 



示例 1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2：

输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：

输入：["a==b","b==c","a==c"]
输出：true
示例 4：

输入：["a==b","b!=c","c==a"]
输出：false
示例 5：

输入：["c==c","b==d","x!=z"]
输出：true


提示：

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 '='，要么是 '!'
equations[i][2] 是 '='

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/satisfiability-of-equality-equations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

684.冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。



示例 1：



输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
示例 2：



输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]


提示:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1319.联通网络的操作次数

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 



示例 1：



输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：



输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2
示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。
示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0


提示：

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

128.最长连续序列

947.移除最多的同行或同列石头

721.账户合并

765.情侣牵手

685.冗余连接II