并查集（Disjoint set，Union-Find）是一种用来管理元素分组情况的数据结构。并查集的一种高效实现是：使用树的根节点「代表」一个集合，同一棵树上的所有节点属于一个集合。只要两个元素的根节点相同，就视为属于同一个集合。使用树的根节点代表一个集合的方法，称之为「代表元」法。

  • 初始化（Init）：将每个元素所在集合初始化为其自身。
  • 合并（Union）：将两个元素所属的集合合并为一个集合。
  • 查找（Find）：查找元素所在的集合，即根节点。

应用

  • 最小生成树：Kruskal 算法
  • 图的联通分量
  • 动态联通性格
  • 二分图判断等

局限

  • 不支持拆分（split）操作：任何节点一旦成为其他节点的子节点后，将永远不可能再成为树根。
  • 集合必须是不相交的（disjoint）：同一个元素不能属于多个集合。
  • 代表元不记录集合成员信息：
    • 父节点不记录子节点的信息。
    • 查找图中某节点所在的连通分量的所有节点需要再次扫描或者维护额外信息。

代码模板

  1.  //并查集  init(n)，Find(x) 以及 Union(x, y) 函数，分别对应初始化，查找，合并操作
  2.     class UnionFind {
  3.         int count;
  4.         int[] parent;
  5.         int[] rank;
  6.         //init初始化
  7.         public UnionFind(int n) {
  8.             //连通分量个数
  9.             count = 0;
  10.             //集合的代表元素 parent 数组
  11.             parent = new int[n];
  12.             /*考虑到优化并查集的算法时间复杂度可以采用路径压缩和按秩合并两种方式
  13.             下面使用按秩合并，为了实现按秩合并，秩是衡量一颗树的指标，它可以是树中节点数，
  14.             也可以是树的最大深度。我们使用 rank 数组记录额外信息*/
  15.             rank = new int[n];
  16.             for (int i = 0; i < n; ++i) {
  17.                 // 初始时每个集合的代表元素就是自身
  18.                 parent[i] = i;
  19.                 ++count;   
  20.                 //初始化的时候每个集合节点rank都一样 只有一个元素 
  21.                 rank[i] = 1;     
  22.             }
  23.         }
  24.         //最坏情况下树退化为链 Find 函数最坏时间复杂度是：O(n)，n 为节点数。
  25.         /* 查找 x 所在集合的代表元素，即父节点 */
  26.         public int find(int x) {
  27.             while (x != parent[x]) {
  28.                // 不断循环查找根结点
  29.                x = parent[x];
  30.             }
  31.             return parent[x];
  32.         }
  34.         /* union函数 合并 x y 所在集合 */
  35.         public void union(int x, int y) {
  36.             //查询x所在集合
  37.             int rootx = find(x);
  38.             //查询y所在集合
  39.             int rooty = find(y);
  40.             if (rootx != rooty) {
  41.                 // x 所在集合比 y 所在集合节点数多
  42.                 // 将 y 所在集合合并到 x 所在集合，并更新 x 所在集合的节点数信息
  43.                 if (rank[rootx] > rank[rooty]) {
  44.                     parent[rooty] = rootx;
  45.                     rank[rootx] +=rank[rooty];
  46.                 } else {
  47.                     // x 所在集合不比 y 所在集合节点数多
  48.                     // 将 x 所在集合合并到 y 所在集合,并更新y所在集合的信息
  49.                     parent[rootx] = rooty;
  50.                     rank[rooty] += rank[x];
  51.                 }
  52.                 //合并一次就要减少一次连通分量的个数
  53.                 --count;
  54.             }
  55.         }
  56.         //返回连通分量个数
  57.         public int getCount() {
  58.             return count;
  59.         }
  60.         // 判断两个节点是否在一个连通分量里面
  61.         public boolean isConnect(int x,int y){
  62.             int rootx = find(x),rooty = find(y);
  63.             return rootx == rooty;
  64.         }
  65.     }

例题1：

lc785 二分图的判定 https://leetcode-cn.com/problems/is-graph-bipartite/
IMG20211112175730.png

AC 代码

  1. class Solution {
  2.     public boolean isBipartite(int[][] graph) {
  3.         int len = graph.length;
  4.         // 初始化并查集
  5.         UnionFind uf = new UnionFind(len);
  6.         // 遍历每个顶点，将当前顶点的所有邻接点进行合并
  7.         for (int i = 0; i < len; i++) {
  8.             int[] adjs = graph[i];
  9.             // 遍历该顶点的邻接点
  10.             for (int w: adjs) {
  11.                 // 若某个邻接点与当前顶点已经在一个集合中了，说明不是二分图，返回 false。
  12.                 if (uf.isConnected(i, w)) {
  13.                     return false;
  14.                 }
  15.                 // 所有邻接点进行合并
  16.                 uf.union(adjs[0], w);
  17.             }
  18.         }
  19.         return true;
  20.     }
  21. }
  23. // 并查集
  24. class UnionFind {
  25.     int[] roots;
  26.     public UnionFind(int n) {
  27.         roots = new int[n]; 
  28.         for (int i = 0; i < n; i++) {
  29.             roots[i] = i;
  30.         }
  31.     }
  33.     public int find(int i) {
  34.         if (roots[i] == i) {
  35.             return i;
  36.         }
  37.         return roots[i] = find(roots[i]);
  38.     }
  40.     // 判断 p 和 q 是否在同一个集合中
  41.     public boolean isConnected(int p, int q) {
  42.         return find(q) == find(p);
  43.     }
  45.     // 合并 p 和 q 到一个集合中
  46.     public void union(int p, int q) {
  47.         roots[find(p)] = find(q);
  48.     }
  49. }

例题二

lc839：https://leetcode-cn.com/problems/similar-string-groups/

IMG20211113114612.png
思路将每个字符串看成图中的一个顶点，判断是否为相似的字符串，如果相似则用并查集合并
最后检查并查集里面有多少连通分量，即相似的字符串组

AC代码：

  1. class Solution {
  2.     public int numSimilarGroups(String[] strs) {
  3.         int len = strs.length;
  4.         int strlen = strs[0].length();
  5.         UnionFind uf = new UnionFind(len);
  6.         for(int i=0;i<len;i++){
  7.             for(int j=i+1;j<len;j++){
  8.                 // 如果两个点已经在一个连通分量里面了 就不需要合并了
  9.                 if(uf.isConnect(i,j))continue;
  11.                 if(check(strs[i],strs[j],strlen)){
  12.                     // 合并两个字符串
  13.                     uf.union(i,j);
  14.                 }
  15.             }
  16.         }
  17.         // 返回连通分量个数
  18.         return uf.getCount();
  20.     }
  22.     // 判断给定字符串是否相似
  23.     public boolean check(String a, String b, int len) {
  24.         int num = 0;
  25.         for (int i = 0; i < len; i++) {
  26.             if (a.charAt(i) != b.charAt(i)) {
  27.                 num++;
  28.                 if (num > 2) {
  29.                     return false;
  30.                 }
  31.             }
  32.         }
  33.         return num == 0 || num == 2;
  34.     }
  37.     class UnionFind {
  38.         int count;
  39.         int[] parent;
  40.         int[] rank;
  42.         public UnionFind(int n) {
  43.             //连通分量个数
  44.             count = 0;
  45.             parent = new int[n];
  46.             rank = new int[n];
  47.             for (int i = 0; i < n; ++i) {
  48.                 parent[i] = i;
  49.                 ++count;   
  50.                 rank[i] = 1;     
  51.             }
  52.         }
  54.         public int find(int x) {
  55.             while (x != parent[x]) {
  56.                x = parent[x];
  57.             }
  58.             return parent[x];
  59.         }
  61.         public void union(int x, int y) {
  62.             int rootx = find(x);
  63.             int rooty = find(y);
  64.             if (rootx != rooty) {
  65.                 if (rank[rootx] > rank[rooty]) {
  66.                     parent[rooty] = rootx;
  67.                     rank[rootx] +=rank[rooty];
  68.                 } else {
  69.                     parent[rootx] = rooty;
  70.                     rank[rooty] += rank[x];
  71.                 }
  72.                 //合并一次就要减少一次连通分量的个数
  73.                 --count;
  74.             }
  75.         }
  76.         //返回连通分量个数
  77.         public int getCount() {
  78.             return count;
  79.         }
  80.         // 判断两个节点是否在一个连通分量里面
  81.         public boolean isConnect(int x,int y){
  82.             int rootx = find(x),rooty = find(y);
  83.             return rootx == rooty;
  84.         }
  85.     }
  87. }

IMG20211113114832.png

并查集的时间复杂度

理论上，「路径压缩」与「按秩合并」，
执行 m次 Find操作, n-1 次 union操作的时间复杂度是 数据结构之【并查集】 - 图4，
其中 数据结构之【并查集】 - 图5 数据结构之【并查集】 - 图6 是反阿克曼函数。
反阿克曼函数是一个渐进复杂度很低的函数，通常可以认为是 常数级别的时间复杂度。感兴趣的可以自行查询
Theorem. [Tarjan 1975] Link-by-size with path compression performs any intermixed sequence of m \geq nm≥n FIND and n-1n−1 UNION operations in O(m \space \alpha(m, n))O(m α(m,n)) time, where \alpha(m, n)α(m,n) is a functional inverse of the Ackermann function. [1, 2]