并查集（Union-Find）数据结构

本次围绕并查集的核心概念、实现方法、习题应用展开讨论，明确了并查集的实际使用场景与解题思路，以下是详细总结内容。

一、 核心内容总结

（一）并查集的定义与应用场景

1. 定义：并查集是一种抽象数据类型（ADT），专门用于处理n 个不同元素的不相交集合的合并（Union）与查询（Find）问题，能高效管理元素的所属集合关系。
2. 应用场景：适用于需要动态维护集合归属、判断元素是否同属一个集合的场景。例如：公司校招学生组队（从互不相识的小分队合并为朋友圈）、城市连通性（省份划分）、变量等式 / 不等式关系校验等。

（二）并查集的数组表示方式

并查集的底层通常采用一维数组实现，利用数组下标与值的映射关系存储集合信息，具体规则如下：

1. 初始化：将元素进行唯一编号后，数组初始值全部设为-1（数组下标对应元素编号，如parent[0]对应元素 0）。
2. 数值含义：
   • 若数组值为负数：该下标是当前集合的根节点，负号仅表示 “根”，数字的绝对值表示集合中元素的个数（如parent[2] = -5表示元素 2 是根节点，对应集合有 5 个元素）。
   • 若数组值为非负数：该下标对应的元素不是根节点，值表示其父节点在数组中的下标（如parent[3] = 2表示元素 3 的父节点是元素 2）。

（三）并查集的核心操作实现

并查集的核心是查找（Find）和合并（Union），基于这两个操作可延伸出 “判断是否同集”“统计集合个数” 等功能：

1. 查找根节点：从目标元素出发，不断向上查找其父节点，直到找到值为负数的根节点（若输入下标为负数，抛出异常，因为元素编号为非负）。
2. 判断是否同集：分别查找两个元素的根节点，若根节点相同则同属一个集合，否则不属于。
3. 合并两个集合：先找到两个元素的根节点，若根节点不同则进行合并（将一个根节点的值更新为两个根节点值之和，另一个根节点的父节点指向该根节点）。
4. 统计集合个数：遍历数组，统计其中负数的个数（每个负数对应一个根节点，即一个集合）。

（四）典型习题解题思路

会议讲解了两道并查集经典习题，核心是将实际问题转化为集合的合并与查询：

1. 省份数量问题
   • 问题描述：给定 n 个城市的相连关系矩阵（矩阵中i行j列=1表示第 i 个城市和第 j 个城市直接相连），求省份的数量（省份是由直接 / 间接相连的城市组成的集合）。
   • 解题思路：遍历矩阵，若matrix[i][j]=1，则将城市 i 和城市 j 合并；遍历完成后，统计并查集数组中负数的个数，即为省份数量。
2. 等式方程的可满足性问题
   • 问题描述：给定由变量关系字符串组成的数组（方程形式为a==b或a!=b），判断所有方程是否能同时成立。
   • 解题思路：分两步处理，第一步遍历所有==方程，将等号连接的变量合并到同一集合；第二步遍历所有!=方程，检查不等号连接的变量是否在同一集合（若在则方程不成立，返回false；否则返回true）。

二、重难点分析与通俗注释

（一）重点 1：并查集数组的数值含义（难点：根节点与普通节点的数值区别）

• 核心要点：数组的下标是元素的 “身份证号”，值是元素的 “归属信息”。
• 通俗注释：可以把集合想象成 “家族”，根节点是 “族长”。数组值为负数时，这个元素是族长，数字的绝对值是家族人数；数组值为正数时，这个元素是家族成员，值是族长的 “身份证号”（或上一级成员的身份证号）。比如parent[5] = 3表示元素 5 的上级是元素 3，parent[3] = -4表示元素 3 是族长，家族有 4 个人。

（二）重点 2：查找根节点的逻辑（可拓展：路径压缩优化，提升效率）

• 核心要点：查找的终点是根节点（值为负数），基础版查找是线性遍历，优化版可通过 “路径压缩” 让元素直接指向根节点。
• 通俗注释：就像找族长，基础版是 “你问你爸→爸问爷爷→爷爷问族长”，要走好几步；路径压缩是 “你直接记下班族长的手机号”，下次找族长直接联系，不用再层层询问，效率更高。

（三）重点 3：合并两个集合的核心规则（难点：根节点的合并而非普通节点）

• 核心要点：合并的是两个集合的根节点，不是普通元素；合并时要将一个根节点的父节点指向另一个根节点，并更新集合大小。
• 通俗注释：两个家族合并，只能是族长之间商量合并，不能让家族里的普通成员说了算。比如 A 家族族长是 3（家族有 5 人），B 家族族长是 7（家族有 3 人），合并后可以让 7 的父节点是 3，同时 3 的值变为-8（5+3），表示合并后的家族有 8 人。

（四）重点 4：实际问题转化为并查集问题的思路（难点：如何将业务场景映射为集合的合并与查询）

• 核心要点：先明确问题中的 “元素” 是什么，再确定 “哪些元素需要合并为一个集合”，最后通过查询 / 统计集合数解决问题。
• 通俗注释：比如省份数量问题，“元素” 是城市，“两个城市相连” 就是 “合并两个元素”，“省份数量” 就是 “集合的个数”；等式方程问题，“元素” 是变量（a、b 等），“a==b” 是 “合并 a 和 b”，“a!=b” 是 “查询 a 和 b 是否不同集”。

三、Java 代码实现（带详细注释）

以下代码采用 Java 实现，包含并查集基础类、优化类（路径压缩 + 按秩合并），以及两道经典习题的解题代码。

（一）并查集基础类（基础版）

java

运行

/** * 并查集基础实现类（线性查找，未优化合并） */ public class UnionFind { private int[] parent; /** * 构造方法：初始化并查集 * @param n 元素个数 */ public UnionFind(int n) { // 初始化并查集数组，初始值全为-1 parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = -1; } } /** * 查找元素x的根节点（基础版：线性查找） * @param x 目标元素 * @return 根节点下标 * @throws IllegalArgumentException 输入下标非法时抛出 */ public int find(int x) { if (x < 0 || x >= parent.length) { throw new IllegalArgumentException("元素下标超出范围"); } // 循环查找父节点，直到找到根节点（值为负数） while (parent[x] >= 0) { x = parent[x]; } return x; } /** * 判断元素x和y是否在同一集合 * @param x 元素x * @param y 元素y * @return true：同集；false：不同集 */ public boolean isSameSet(int x, int y) { return find(x) == find(y); } /** * 合并元素x和y所在的集合 * @param x 元素x * @param y 元素y */ public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { // 已在同一集合，无需合并 return; } // 合并规则：将rootY的父节点设为rootX，更新rootX的集合大小 parent[rootX] += parent[rootY]; parent[rootY] = rootX; } /** * 统计集合的个数 * @return 集合数量 */ public int getSetCount() { int count = 0; for (int val : parent) { if (val < 0) { count++; } } return count; } }

（二）并查集优化类（路径压缩 + 按秩合并，效率更高）

java

运行

/** * 并查集优化实现类（路径压缩 + 按秩合并） */ public class UnionFindOptimized { private int[] parent; private int[] rank; // 存储集合的高度（秩） /** * 构造方法：初始化并查集 * @param n 元素个数 */ public UnionFindOptimized(int n) { // parent数组：初始值为自身（根节点指向自己） parent = new int[n]; // rank数组：初始值为1（每个集合的高度初始为1） rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } } /** * 查找元素x的根节点（路径压缩：迭代版，避免递归栈溢出） * @param x 目标元素 * @return 根节点下标 * @throws IllegalArgumentException 输入下标非法时抛出 */ public int find(int x) { if (x < 0 || x >= parent.length) { throw new IllegalArgumentException("元素下标超出范围"); } // 路径压缩：将x的父节点直接设为根节点 if (parent[x] != x) { parent[x] = find(parent[x]); // 递归版路径压缩（简洁，小数据量推荐） // 迭代版路径压缩（大数据量推荐，避免栈溢出） /* int root = x; // 先找到根节点 while (parent[root] != root) { root = parent[root]; } // 路径压缩：将沿途节点的父节点都设为根节点 while (parent[x] != root) { int temp = parent[x]; parent[x] = root; x = temp; } return root; */ } return parent[x]; } /** * 判断元素x和y是否在同一集合 * @param x 元素x * @param y 元素y * @return true：同集；false：不同集 */ public boolean isSameSet(int x, int y) { return find(x) == find(y); } /** * 合并元素x和y所在的集合（按秩合并：小秩合并到大秩下） * @param x 元素x * @param y 元素y */ public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } // 按秩合并：高度小的集合合并到高度大的集合下，保持树的高度最小 if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else { // 高度相同，合并后高度+1 parent[rootY] = rootX; rank[rootX]++; } } /** * 统计集合的个数 * @return 集合数量 */ public int getSetCount() { int count = 0; for (int i = 0; i < parent.length; i++) { // 根节点的特征是parent[i] == i if (parent[i] == i) { count++; } } return count; } }

（三）习题 1：省份数量

java

运行

/** * 省份数量问题求解 */ public class ProvinceCount { /** * 求解省份数量 * @param isConnected 城市的相连关系矩阵 * @return 省份数量 */ public static int findCircleNum(int[][] isConnected) { int n = isConnected.length; // 初始化并查集（这里用优化版，也可用基础版） UnionFindOptimized uf = new UnionFindOptimized(n); // 遍历矩阵（仅遍历上三角，避免重复合并） for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (isConnected[i][j] == 1) { uf.union(i, j); } } } // 返回集合个数，即省份数量 return uf.getSetCount(); } // 测试用例 public static void main(String[] args) { int[][] testMatrix = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}; System.out.println("省份数量：" + findCircleNum(testMatrix)); // 输出：2 } }

（四）习题 2：等式方程的可满足性

java

运行

/** * 等式方程的可满足性问题求解 */ public class EquationPossible { /** * 判断等式方程是否可满足 * @param equations 等式/不等式数组 * @return true：可满足；false：不可满足 */ public static boolean equationsPossible(String[] equations) { // 变量是小写字母，共26个，映射为0-25的下标 UnionFindOptimized uf = new UnionFindOptimized(26); // 第一步：处理所有==方程，合并变量 for (String eq : equations) { if (eq.charAt(1) == '=') { // 字符转下标：'a'->0，'b'->1，...，'z'->25 int x = eq.charAt(0) - 'a'; int y = eq.charAt(3) - 'a'; uf.union(x, y); } } // 第二步：处理所有!=方程，检查是否同集 for (String eq : equations) { if (eq.charAt(1) == '!') { int x = eq.charAt(0) - 'a'; int y = eq.charAt(3) - 'a'; if (uf.isSameSet(x, y)) { return false; } } } // 所有检查通过，返回True return true; } // 测试用例 public static void main(String[] args) { String[] testEquations1 = {"a==b", "b!=a"}; System.out.println(equationsPossible(testEquations1)); // 输出：false String[] testEquations2 = {"a==b", "b==c", "a==c"}; System.out.println(equationsPossible(testEquations2)); // 输出：true } }