定义

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并（Union）：把两个不相交的集合合并为一个集合。 查询（Find）：查询两个元素是否在同一个集合中。

初始化

  1. int fa[MAXN];
  2. inline void init(int n)
  3. {
  4.     for (int i = 1; i <= n; ++i)
  5.         fa[i] = i;
  6. }

查询

  1. int find(int x)
  2. {
  3.     if(fa[x] == x)
  4.         return x;
  5.     else
  6.         return find(fa[x]);
  7. }

合并(用此方法合并 i 到 j)

  1. inline void union(int i, int j)
  2. {
  3.     fa[find(i)] = find(j);//并查集合并
  4. }

合并查询（Find）（路径压缩）

  1. int find(int x)
  2. {
  3.     return x == fa[x] ? x : (fa[x] = find(fa[x]));
  4. }

按秩合并

我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。 我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用，时间复杂度接近并查集 - 图1，但是很可能会破坏rank的准确性。

初始化（按秩合并）

  1. inline void init(int n)
  2. {
  3.     for (int i = 0; i < n; ++i)
  4.     {
  5.         fa[i] = i;
  6.         rank[i] = 1;
  7.     }
  8. }

合并（按秩合并）

  1. inline void merge(int i, int j)
  2. {
  3.     int x = find(i), y = find(j);    //先找到两个根节点
  4.     if (rank[x] <= rank[y])
  5.         fa[x] = y;
  6.     else
  7.         fa[y] = x;
  8.     if (rank[x] == rank[y] && x != y)
  9.         rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
  10. }

最后总结

  1. class UF {
  2.     // 连通分量个数
  3.      int count;
  4.     // 存储一棵树
  5.      int* fa;
  6.     // 记录树的“重量”
  7.     int* rank;
  8. public :
  9.       UF(int n) {
  10.         this.count = n;
  11.         fa = new int[n];
  12.         size = new int[n];
  13.         for (int i = 0; i < n; i++) {
  14.             fa[i] = i;
  15.             rank[i] = 1;
  16.         }
  17.     }
  19.      void merge(int p, int q) {
  20.         int rootP = find(p);
  21.         int rootQ = find(q);
  22.         if (rootP == rootQ)
  23.             return;
  25.         // 小树接到大树下面，较平衡
  26.         if (rank[rootP] > rank[rootQ]) {
  27.             fa[rootQ] = rootP;
  28.         } else {
  29.             fa[rootP] = rootQ;
  30.         }
  31.         //如果深度相同且根节点不同，则新的根节点的深度+1
  32.         if (rank[rootQ] == rank[rootP])
  33.             rank[rootQ]++;    
  34.         count--;
  35.     }
  37.      boolean connected(int p, int q) {
  38.         int rootP = find(p);
  39.         int rootQ = find(q);
  40.         return rootP == rootQ;
  41.     }
  43.      int find(int x){
  44.         return x==fa[x]?x:(fa[x]=find(fa[x]));
  45.     }
  46. }

或者

  1. class UF {
  2.     // 连通分量个数
  3.      int count;
  4.     // 存储一棵树
  5.      int* fa;
  6.     // 记录树的“重量”
  7.     int* rank;
  8. public :
  9.       UF(int n) {
  10.         this.count = n;
  11.         fa = new int[n];
  12.         size = new int[n];
  13.         for (int i = 0; i < n; i++) {
  14.             fa[i] = i;
  15.             rank[i] = 1;
  16.         }
  17.     }
  19.      void union(int p, int q) {
  20.         int rootP = find(p);
  21.         int rootQ = find(q);
  22.         if (rootP == rootQ)
  23.             return;
  25.         // 小树接到大树下面，较平衡
  26.         if (rank[rootP] > rank[rootQ]) {
  27.             fa[rootQ] = rootP;
  28.             rank[rootP] += rank[rootQ];
  29.         } else {
  30.             fa[rootP] = rootQ;
  31.             rank[rootQ] += rank[rootP];
  32.         }
  33.         count--;
  34.     }
  36.      boolean connected(int p, int q) {
  37.         int rootP = find(p);
  38.         int rootQ = find(q);
  39.         return rootP == rootQ;
  40.     }
  42.      int find(int x) {
  43.         while (f[x] != x) {
  44.             // 进行路径压缩
  45.             f[x] = f[parent[x]];
  46.             x = parent[x];
  47.         }
  48.         return x;
  49.     }
  50. }

例子

一、（洛谷P1551）亲戚

题目背景 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 题目描述 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 输入格式 第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。 输出格式 P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

  1. #include <cstdio>
  2. #define MAXN 5005
  3. int fa[MAXN], rank[MAXN];
  4. inline void init(int n)
  5. {
  6.     for (int i = 1; i <= n; ++i)
  7.     {
  8.         fa[i] = i;
  9.         rank[i] = 1;
  10.     }
  11. }
  12. int find(int x)
  13. {
  14.     return x == fa[x] ? x : (fa[x] = find(fa[x]));
  15. }
  16. inline void merge(int i, int j)
  17. {
  18.     int x = find(i), y = find(j);
  19.     if (rank[x] <= rank[y])
  20.         fa[x] = y;
  21.     else
  22.         fa[y] = x;
  23.     if (rank[x] == rank[y] && x != y)
  24.         rank[y]++;
  25. }
  26. int main()
  27. {
  28.     int n, m, p, x, y;
  29.     scanf("%d%d%d", &n, &m, &p);
  30.     init(n);
  31.     for (int i = 0; i < m; ++i)
  32.     {
  33.         scanf("%d%d", &x, &y);
  34.         merge(x, y);
  35.     }
  36.     for (int i = 0; i < p; ++i)
  37.     {
  38.         scanf("%d%d", &x, &y);
  39.         printf("%s\n", find(x) == find(y) ? "Yes" : "No");
  40.     }
  41.     return 0;
  42. }

二、（NOIP提高组2017年D2T1） 洛谷P3958 奶酪

题目描述

现有一块大奶酪，它的高度为并查集 - 图2，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为并查集 - 图3 ，奶酪的上表面为 并查集 - 图4。 现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。 位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑到奶酪的上表面去? 空间内两点 并查集 - 图5 、 并查集 - 图6的距离公式如下： 并查集 - 图7

输入格式 每个输入文件包含多组数据。接下来的第一行，包含一个正整数 并查集 - 图8 ，代表该输入文件中所含的数据组数。 接下来是 并查集 - 图9组数据，每组数据的格式如下： 第一行包含三个正整数 并查集 - 图10和 并查集 - 图11 ，两个数之间以一个空格分开，分别代表奶酪中空 洞的数量，奶酪的高度和空洞的半径。 接下来的并查集 - 图12 行，每行包含三个整数 并查集 - 图13，两个数之间以一个空格分开，表示空 洞球心坐标为 并查集 - 图14 。

输出格式 并查集 - 图15行，分别对应并查集 - 图16组数据的答案，如果在第 并查集 - 图17 组数据中，Jerry 能从下表面跑到上表面，则输出Yes，如果不能，则输出No（均不包含引号）。

我们把所有空洞划分为若干个集合，一旦两个空洞相交或相切，就把它们放到同一个集合中。

我们还可以划出2个特殊元素，分别表示底部和顶部，如果一个空洞与底部接触，则把它与表示底部的元素放在同一个集合中，顶部同理。最后，只需要看顶部和底部是不是在同一个集合中即可。这完全可以通过并查集实现。来看代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #define MAXN 1005
  4. typedef long long ll;
  5. int fa[MAXN], rank[MAXN];
  6. ll X[MAXN], Y[MAXN], Z[MAXN];
  7. inline bool next_to(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2, ll r)
  8. {
  9.     return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2) <= 4 * r * r;
  10.     //判断两个空洞是否相交或相切
  11. }
  12. inline void init(int n)
  13. {
  14.     for (int i = 1; i <= n; ++i)
  15.     {
  16.         fa[i] = i;
  17.         rank[i] = 1;
  18.     }
  19. }
  20. int find(int x)
  21. {
  22.     return x == fa[x] ? x : (fa[x] = find(fa[x]));
  23. }
  24. inline void merge(int i, int j)
  25. {
  26.     int x = find(i), y = find(j);
  27.     if (rank[x] <= rank[y])
  28.         fa[x] = y;
  29.     else
  30.         fa[y] = x;
  31.     if (rank[x] == rank[y] && x != y)
  32.         rank[y]++;
  33. }
  34. int main()
  35. {
  36.     int T, n, h;
  37.     ll r;
  38.     scanf("%d", &T);
  39.     for (int I = 0; I < T; ++I)
  40.     {
  41.         memset(X, 0, sizeof(X));
  42.         memset(Y, 0, sizeof(Y));
  43.         memset(Z, 0, sizeof(Z));
  44.         scanf("%d%d%lld", &n, &h, &r);
  45.         init(n);
  46.         fa[1001] = 1001; //用1001代表底部
  47.         fa[1002] = 1002; //用1002代表顶部
  48.         for (int i = 1; i <= n; ++i)
  49.             scanf("%lld%lld%lld", X + i, Y + i, Z + i);
  50.         for (int i = 1; i <= n; ++i)
  51.         {
  52.             if (Z[i] <= r)
  53.                 merge(i, 1001); //与底部接触的空洞与底部合并
  54.             if (Z[i] + r >= h)
  55.                 merge(i, 1002); //与顶部接触的空洞与顶部合并
  56.         }
  57.         for (int i = 1; i <= n; ++i)
  58.         {
  59.             for (int j = i + 1; j <= n; ++j)
  60.             {
  61.                 if (next_to(X[i], Y[i], Z[i], X[j], Y[j], Z[j], r))
  62.                     merge(i, j); //遍历所有空洞，合并相交或相切的球
  63.             }
  64.         }
  65.         printf("%s\n", find(1001) == find(1002) ? "Yes" : "No");
  66.     }
  67.     return 0;
  68. }

三、DFS 的替代方案

很多使用 DFS 深度优先算法解决的问题，也可以用 Union-Find 算法解决。

比如第 130 题，被围绕的区域：给你一个 M×N 的二维矩阵，其中包含字符X和O，让你找到矩阵中完全被X围住的O，并且把它们替换成X。 并查集 - 图18

  1. void solve(char[][] board);

注意哦，必须是完全被围的O才能被换成X，也就是说边角上的O一定不会被围，进一步，与边角上的O相连的O也不会被X围四面，也不会被替换：

image.png

解决这个问题的传统方法也不困难，先用 for 循环遍历棋盘的四边，用 DFS 算法把那些与边界相连的O换成一个特殊字符，比如#；然后再遍历整个棋盘，把剩下的O换成X，把#恢复成O。这样就能完成题目的要求，时间复杂度 O(MN)。

  1. class Solution {
  2. public:
  3.     void solve(vector<vector<char>>& board) {
  4.         if (board.empty() || board[0].empty()) return;
  5.         int m = board.size(), n = board[0].size();
  6.         for (int i = 0; i < m; ++i) {
  7.             for (int j = 0; j < n; ++j) {
  8.                 if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
  9.                     if (board[i][j] == 'O') dfs(board, i , j);
  10.                 }
  11.             }   
  12.         }
  13.         for (int i = 0; i < m; ++i) {
  14.             for (int j = 0; j < n; ++j) {
  15.                 if (board[i][j] == 'O') board[i][j] = 'X';
  16.                 if (board[i][j] == '$') board[i][j] = 'O';
  17.             }
  18.         }
  19.     }
  20.     void dfs(vector<vector<char>> &board, int x, int y) {
  21.         int m = board.size(), n = board[0].size();
  22.         vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
  23.         board[x][y] = '$';
  24.         for (int i = 0; i < dir.size(); ++i) {
  25.             int dx = x + dir[i][0], dy = y + dir[i][1];
  26.             if (dx >= 0 && dx < m && dy > 0 && dy < n && board[dx][dy] == 'O') {
  27.                 dfs(board, dx, dy);
  28.             }
  29.         }
  30.     }
  31. };

这个问题也可以用 Union-Find 算法解决，虽然实现复杂一些，甚至效率也略低，但这是使用 Union-Find 算法的通用思想，值得一学。

你可以把那些不需要被替换的**O**看成一个拥有独门绝技的门派，它们有一个共同祖师爷叫**dummy**，这些**O**和**dummy**互相连通，而那些需要被替换的**O**与**dummy**不连通。

这就是 Union-Find 的核心思路，明白这个图，就很容易看懂代码了：

image.png

首先要解决的是，根据我们的实现，Union-Find 底层用的是一维数组，构造函数需要传入这个数组的大小，而题目给的是一个二维棋盘。

这个很简单，二维坐标(x,y)可以转换成x * n + y这个数（m是棋盘的行数，n是棋盘的列数）。敲黑板，这是将二维坐标映射到一维的常用技巧。

其次，我们之前描述的「祖师爷」是虚构的，需要给他老人家留个位置。索引[0.. m*n-1]都是棋盘内坐标的一维映射，那就让这个虚拟的dummy节点占据索引m*n好了。

  1. void solve(char[][] board) {
  2.     if (board.length == 0) return;
  4.     int m = board.length;
  5.     int n = board[0].length;
  6.     // 给 dummy 留一个额外位置
  7.     UF uf = new UF(m * n + 1);
  8.     int dummy = m * n;
  9.     // 将首列和末列的 O 与 dummy 连通
  10.     for (int i = 0; i < m; i++) {
  11.         if (board[i][0] == 'O')
  12.             uf.union(i * n, dummy);
  13.         if (board[i][n - 1] == 'O')
  14.             uf.union(i * n + n - 1, dummy);
  15.     }
  16.     // 将首行和末行的 O 与 dummy 连通
  17.     for (int j = 0; j < n; j++) {
  18.         if (board[0][j] == 'O')
  19.             uf.union(j, dummy);
  20.         if (board[m - 1][j] == 'O')
  21.             uf.union(n * (m - 1) + j, dummy);
  22.     }
  23.     // 方向数组 d 是上下左右搜索的常用手法
  24.     int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
  25.     for (int i = 1; i < m - 1; i++) 
  26.         for (int j = 1; j < n - 1; j++) 
  27.             if (board[i][j] == 'O')
  28.                 // 将此 O 与上下左右的 O 连通
  29.                 for (int k = 0; k < 4; k++) {
  30.                     int x = i + d[k][0];
  31.                     int y = j + d[k][1];
  32.                     if (board[x][y] == 'O')
  33.                         uf.union(x * n + y, i * n + j);
  34.                 }
  35.     // 所有不和 dummy 连通的 O，都要被替换
  36.     for (int i = 1; i < m - 1; i++) 
  37.         for (int j = 1; j < n - 1; j++) 
  38.             if (!uf.connected(dummy, i * n + j))
  39.                 board[i][j] = 'X';
  40. }

这段代码很长，其实就是刚才的思路实现，只有和边界O相连的O才具有和dummy的连通性，他们不会被替换。

说实话，Union-Find 算法解决这个简单的问题有点杀鸡用牛刀，它可以解决更复杂，更具有技巧性的问题，主要思路是适时增加虚拟节点，想办法让元素「分门别类」，建立动态连通关系。

四、判定合法算式

这个问题用 Union-Find 算法就显得十分优美了。题目是这样：

给你一个数组equations，装着若干字符串表示的算式。每个算式equations[i]长度都是 4，而且只有这两种情况：a==b或者a!=b，其中a,b可以是任意小写字母。你写一个算法，如果equations中所有算式都不会互相冲突，返回 true，否则返回 false。

比如说，输入["a==b","b!=c","c==a"]，算法返回 false，因为这三个算式不可能同时正确。

再比如，输入["c==c","b==d","x!=z"]，算法返回 true，因为这三个算式并不会造成逻辑冲突。

我们前文说过，动态连通性其实就是一种等价关系，具有「自反性」「传递性」和「对称性」，其实==关系也是一种等价关系，具有这些性质。所以这个问题用 Union-Find 算法就很自然。

核心思想是，将**equations**中的算式根据**==**和**!=**分成两部分，先处理**==**算式，使得他们通过相等关系各自勾结成门派；然后处理**!=**算式，检查不等关系是否破坏了相等关系的连通性。

  1. boolean equationsPossible(String[] equations) {
  2.     // 26 个英文字母
  3.     UF uf = new UF(26);
  4.     // 先让相等的字母形成连通分量
  5.     for (String eq : equations) {
  6.         if (eq.charAt(1) == '=') {
  7.             char x = eq.charAt(0);
  8.             char y = eq.charAt(3);
  9.             uf.union(x - 'a', y - 'a');
  10.         }
  11.     }
  12.     // 检查不等关系是否打破相等关系的连通性
  13.     for (String eq : equations) {
  14.         if (eq.charAt(1) == '!') {
  15.             char x = eq.charAt(0);
  16.             char y = eq.charAt(3);
  17.             // 如果相等关系成立，就是逻辑冲突
  18.             if (uf.connected(x - 'a', y - 'a'))
  19.                 return false;
  20.         }
  21.     }
  22.     return true;
  23. }

至此，这道判断算式合法性的问题就解决了，借助 Union-Find 算法，是不是很简单呢？

简单总结

使用 Union-Find 算法，主要是如何把原问题转化成图的动态连通性问题。对于算式合法性问题，可以直接利用等价关系，对于棋盘包围问题，则是利用一个虚拟节点，营造出动态连通特性。

另外，将二维数组映射到一维数组，利用方向数组d来简化代码量，都是在写算法时常用的一些小技巧，如果没见过可以注意一下。

很多更复杂的 DFS 算法问题，都可以利用 Union-Find 算法更漂亮的解决。LeetCode 上 Union-Find 相关的问题也就二十多道，有兴趣的读者可以去做一做。