【并查集】

并查集（Disjoint Set Union，DSU）是一种用于处理不相交集合的数据结构，主要支持两种操作：查找（Find）和合并（Union）。它在解决连通性问题、图论问题以及动态连通性等问题时非常有用。

并查集的基础知识

1. 基本概念：

   • 集合：并查集维护一组不相交的集合，每个集合有一个代表元素。
   • 查找（Find）：查找某个元素所属的集合的代表元素。
   • 合并（Union）：将两个集合合并为一个集合。

2. 核心思想：

   • 路径压缩：在查找操作中，将查找路径上的所有节点直接连接到根节点，以加快后续查找操作。
   • 按秩合并：在合并操作中，将较小的树连接到较大的树的根节点上，以保持树的平衡。

3. 时间复杂度：

   • 查找（Find）：接近O(1)（由于路径压缩）。
   • 合并（Union）：接近O(1)（由于按秩合并）。

Python实现

下面是一个简单的并查集实现，包含路径压缩和按秩合并：

class UnionFind:def __init__(self, size):self.parent = list(range(size))  # 初始化每个元素的父节点为自己self.rank = [1] * size  # 初始化每个集合的秩为1def find(self, x):# 查找操作，带路径压缩if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]def union(self, x, y):# 合并操作，带按秩合并rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1# 示例用法
uf = UnionFind(10)
uf.union(1, 2)
uf.union(2, 3)
print(uf.find(1) == uf.find(3))  # 输出: True
print(uf.find(1) == uf.find(4))  # 输出: False

并查集中秩的定义

在进行代码逐行解释之前，我们先来了解rank的知识：
self.rank 是并查集（Union-Find）中的一个重要概念，它用于优化合并操作（union），使得并查集的树结构更加平衡，从而提高查找操作（find）的效率。下面我会详细解释 self.rank 的作用以及它是如何优化并查集的。

---

什么是秩（Rank）？

在并查集中，秩（Rank） 是用来表示集合的“高度”或“大小”的一个指标。具体来说：

• 秩的定义：

  • 对于每个集合（树），秩表示该集合的树的高度（从根节点到最远叶子节点的路径长度）。
  • 初始时，每个集合的秩为 1，因为每个集合只有一个元素（根节点）。

• 秩的作用：

  • 在合并两个集合时，通过比较两个集合的秩，决定如何合并，从而保持树的平衡。
  • 秩越高，表示该集合的树越“深”或“大”，因此应该将较小的树合并到较大的树上。

---

秩的设定与优化

1. 按秩合并（Union by Rank）

在合并两个集合时，我们总是将秩较小的树合并到秩较大的树上。这样做的好处是：

• 避免树的高度过高，从而保证查找操作的时间复杂度接近 O(1)。
• 如果两棵树的秩相同，则合并后秩会增加 1。

2. 秩的更新规则

• 如果 rank[rootX] > rank[rootY]：
  • 将 rootY 的父节点设置为 rootX。
  • rootX 的秩不变。
• 如果 rank[rootX] < rank[rootY]：
  • 将 rootX 的父节点设置为 rootY。
  • rootY 的秩不变。
• 如果 rank[rootX] == rank[rootY]：
  • 将 rootY 的父节点设置为 rootX。
  • rootX 的秩增加 1。

---

秩的作用示例

假设我们有 4 个元素：0, 1, 2, 3，初始时每个元素是一个独立的集合。

初始状态

parent: [0, 1, 2, 3]
rank:   [1, 1, 1, 1]

操作 1：合并 0 和 1

• rank[0] == rank[1]，将 1 的父节点设置为 0，0 的秩增加 1。

parent: [0, 0, 2, 3]
rank:   [2, 1, 1, 1]

操作 2：合并 2 和 3

• rank[2] == rank[3]，将 3 的父节点设置为 2，2 的秩增加 1。

parent: [0, 0, 2, 2]
rank:   [2, 1, 2, 1]

操作 3：合并 1 和 3

• rank[0] == rank[2]，将 2 的父节点设置为 0，0 的秩增加 1。

parent: [0, 0, 0, 2]
rank:   [3, 1, 2, 1]

---

秩的作用总结

1. 保持树的平衡：

   • 通过按秩合并，避免树的高度过高，从而保证查找操作的时间复杂度接近 O(1)。

2. 优化查找操作：

   • 树的高度越低，查找操作的路径越短，路径压缩的效果也越好。

3. 动态调整：

   • 秩会根据合并操作动态调整，始终保持树的平衡。

---

秩与路径压缩的关系

• 路径压缩：
  • 在查找操作中，将路径上的所有节点直接连接到根节点，从而降低树的高度。
• 秩的作用：
  • 在合并操作中，通过按秩合并，避免树的高度过高，从而为路径压缩提供更好的基础。

两者结合，可以显著提高并查集的效率。

---

代码示例

class UnionFind:def __init__(self, size):self.parent = list(range(size))  # 初始化每个元素的父节点为自己self.rank = [1] * size  # 初始化每个集合的秩为1def find(self, x):# 查找操作，带路径压缩if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]def union(self, x, y):# 合并操作，带按秩合并rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1

---

总结

• 秩的作用：通过按秩合并，保持树的平衡，从而优化查找操作。
• 秩的更新规则：在合并时，将较小的树合并到较大的树上，如果秩相同，则增加秩。
• 秩与路径压缩的关系：秩的优化为路径压缩提供了更好的基础，两者结合可以显著提高并查集的效率。

代码解释

• 初始化：parent数组用于存储每个元素的父节点，初始时每个元素的父节点是自己。rank数组用于存储每个集合的秩（树的高度），初始时为1。
• 查找（Find）：通过递归查找元素的根节点，并在查找过程中进行路径压缩，使得后续查找操作更快。
• 合并（Union）：找到两个元素的根节点，如果根节点不同，则将它们合并。合并时根据秩的大小决定如何合并，以保持树的平衡。

应用场景

• 图的连通性问题：判断图中两个节点是否连通。
• 动态连通性问题：在一系列连接操作中，动态判断两个元素是否连通。
• 最小生成树算法：如Kruskal算法中用于判断是否形成环。

并查集代码详细解释

好的！这段代码是一个标准的并查集（Union-Find）实现，包含了路径压缩和按秩合并两种优化。我会逐行详细讲解这段代码，并结合并查集的核心知识帮助你彻底理解。

---

代码逐行讲解

1. 初始化部分

class UnionFind:def __init__(self, size):self.parent = list(range(size))  # 初始化每个元素的父节点为自己self.rank = [1] * size  # 初始化每个集合的秩为1

• self.parent：

  • 这是一个列表，用于存储每个元素的父节点。
  • 初始时，每个元素的父节点是它自己，即 parent[i] = i。
  • 例如，如果 size = 5，则 parent = [0, 1, 2, 3, 4]，表示每个元素初始时是一个独立的集合。

• self.rank：

  • 这是一个列表，用于存储每个集合的秩（树的高度）。
  • 初始时，每个集合的秩为1，因为每个集合只有它自己一个元素。
  • 例如，如果 size = 5，则 rank = [1, 1, 1, 1, 1]。

---

2. 查找操作（Find）

def find(self, x):# 查找操作，带路径压缩if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]

• 功能：

  • 查找元素 x 所在集合的根节点（代表元素）。
  • 在查找过程中，进行路径压缩，将查找路径上的所有节点直接连接到根节点，以加快后续查找操作。

• 逐行解释：

  1. if self.parent[x] != x：
     • 如果 x 的父节点不是它自己，说明 x 不是根节点。
  2. self.parent[x] = self.find(self.parent[x])：
     • 递归查找 x 的根节点，并将 x 的父节点直接设置为根节点（路径压缩）。
  3. return self.parent[x]：
     • 返回 x 的根节点。

• 路径压缩的作用：

  • 将查找路径上的所有节点直接连接到根节点，使得后续查找操作的时间复杂度接近 O(1)。

---

3. 合并操作（Union）

def union(self, x, y):# 合并操作，带按秩合并rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1

• 功能：

  • 将元素 x 和 y 所在的集合合并。
  • 在合并过程中，使用按秩合并，将较小的树合并到较大的树上，以保持树的平衡。

• 逐行解释：

  1. rootX = self.find(x) 和 rootY = self.find(y)：
     • 找到 x 和 y 的根节点。
  2. if rootX != rootY：
     • 如果 x 和 y 不在同一个集合中，才需要合并。
  3. if self.rank[rootX] > self.rank[rootY]：
     • 如果 rootX 的秩大于 rootY 的秩，将 rootY 的父节点设置为 rootX。
  4. elif self.rank[rootX] < self.rank[rootY]：
     • 如果 rootX 的秩小于 rootY 的秩，将 rootX 的父节点设置为 rootY。
  5. else：
     • 如果 rootX 和 rootY 的秩相等，将 rootY 的父节点设置为 rootX，并增加 rootX 的秩。

• 按秩合并的作用：

  • 保持树的平衡，避免树的高度过高，从而保证查找操作的时间复杂度接近 O(1)。

---

好的！下面是一个完整的并查集模板代码，包含路径压缩和按秩合并优化。同时，我会编写测试代码，用大量数据测试并查集的功能，并详细讲解代码的运行过程和结果。

---

完整的并查集模板代码

class UnionFind:def __init__(self, size):self.parent = list(range(size))  # 初始化每个元素的父节点为自己self.rank = [1] * size  # 初始化每个集合的秩为1def find(self, x):# 查找操作，带路径压缩if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]def union(self, x, y):# 合并操作，带按秩合并rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1def is_connected(self, x, y):# 判断两个元素是否在同一个集合中return self.find(x) == self.find(y)

---

测试代码

# 测试并查集功能
def test_union_find():# 初始化并查集，假设有 10 个元素uf = UnionFind(10)# 初始状态print("初始状态：")print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")# 合并操作print("合并 1 和 2：")uf.union(1, 2)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")print("合并 3 和 4：")uf.union(3, 4)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")print("合并 1 和 3：")uf.union(1, 3)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")print("合并 5 和 6：")uf.union(5, 6)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")print("合并 7 和 8：")uf.union(7, 8)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")print("合并 5 和 7：")uf.union(5, 7)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")print("合并 9 和 0：")uf.union(9, 0)print("parent:", uf.parent)print("rank:", uf.rank)print("----------------------------------")# 查找操作print("查找 1 和 4 是否在同一个集合中：", uf.is_connected(1, 4))print("查找 5 和 8 是否在同一个集合中：", uf.is_connected(5, 8))print("查找 0 和 9 是否在同一个集合中：", uf.is_connected(0, 9))print("查找 2 和 6 是否在同一个集合中：", uf.is_connected(2, 6))print("----------------------------------")# 最终状态print("最终状态：")print("parent:", uf.parent)print("rank:", uf.rank)# 运行测试
test_union_find()

---

代码运行过程与结果

初始状态

初始状态：
parent: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
rank: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

• 每个元素的父节点是自己，秩为1。

---

合并 1 和 2

合并 1 和 2：
parent: [0, 1, 1, 3, 4, 5, 6, 7, 8, 9]
rank: [1, 2, 1, 1, 1, 1, 1, 1, 1, 1]

• 将 2 的父节点设置为 1，1 的秩增加为2。

---

合并 3 和 4

合并 3 和 4：
parent: [0, 1, 1, 3, 3, 5, 6, 7, 8, 9]
rank: [1, 2, 1, 2, 1, 1, 1, 1, 1, 1]

• 将 4 的父节点设置为 3，3 的秩增加为2。

---

合并 1 和 3

合并 1 和 3：
parent: [0, 1, 1, 1, 3, 5, 6, 7, 8, 9]
rank: [1, 3, 1, 2, 1, 1, 1, 1, 1, 1]

• 将 3 的父节点设置为 1，1 的秩增加为3。

---

合并 5 和 6

合并 5 和 6：
parent: [0, 1, 1, 1, 3, 5, 5, 7, 8, 9]
rank: [1, 3, 1, 2, 1, 2, 1, 1, 1, 1]

• 将 6 的父节点设置为 5，5 的秩增加为2。

---

合并 7 和 8

合并 7 和 8：
parent: [0, 1, 1, 1, 3, 5, 5, 7, 7, 9]
rank: [1, 3, 1, 2, 1, 2, 1, 2, 1, 1]

• 将 8 的父节点设置为 7，7 的秩增加为2。

---

合并 5 和 7

合并 5 和 7：
parent: [0, 1, 1, 1, 3, 5, 5, 5, 7, 9]
rank: [1, 3, 1, 2, 1, 3, 1, 2, 1, 1]

• 将 7 的父节点设置为 5，5 的秩增加为3。

---

合并 9 和 0

合并 9 和 0：
parent: [0, 1, 1, 1, 3, 5, 5, 5, 7, 0]
rank: [2, 3, 1, 2, 1, 3, 1, 2, 1, 1]

• 将 9 的父节点设置为 0，0 的秩增加为2。

---

查找操作

查找 1 和 4 是否在同一个集合中： True
查找 5 和 8 是否在同一个集合中： True
查找 0 和 9 是否在同一个集合中： True
查找 2 和 6 是否在同一个集合中： False

• 1 和 4 在同一个集合中（根节点都是 1）。
• 5 和 8 在同一个集合中（根节点都是 5）。
• 0 和 9 在同一个集合中（根节点都是 0）。
• 2 和 6 不在同一个集合中（根节点分别是 1 和 5）。

---

最终状态

最终状态：
parent: [0, 1, 1, 1, 3, 5, 5, 5, 7, 0]
rank: [2, 3, 1, 2, 1, 3, 1, 2, 1, 1]

• 最终并查集的状态反映了所有合并操作的结果。

---

总结

通过这段代码和测试，你可以清晰地看到并查集的工作过程：

1. 初始化：每个元素是一个独立的集合。
2. 合并操作：将两个集合合并为一个集合，同时更新秩。
3. 查找操作：判断两个元素是否在同一个集合中，同时进行路径压缩。

希望这段详细的讲解和测试代码能帮助你彻底理解并查集！如果还有疑问，欢迎继续提问！

并查集的核心知识回顾

1. 集合的表示：

   • 每个集合用一棵树表示，树的根节点是集合的“代表元素”。
   • 每个节点都有一个父节点，根节点的父节点是它自己。

2. 查找操作（Find）：

   • 查找某个元素所在集合的根节点。
   • 使用路径压缩优化，将查找路径上的所有节点直接连接到根节点。

3. 合并操作（Union）：

   • 将两个集合合并为一个集合。
   • 使用按秩合并优化，将较小的树合并到较大的树上。

---

示例演示

假设我们有 5 个元素：0, 1, 2, 3, 4，初始时每个元素是一个独立的集合。

初始化

parent = [0, 1, 2, 3, 4]
rank = [1, 1, 1, 1, 1]

操作 1：合并 0 和 1

union(0, 1)

• 找到 0 的根节点是 0，1 的根节点是 1。
• 因为 rank[0] == rank[1]，将 1 的父节点设置为 0，并增加 rank[0]。

parent = [0, 0, 2, 3, 4]
rank = [2, 1, 1, 1, 1]

操作 2：合并 2 和 3

union(2, 3)

• 找到 2 的根节点是 2，3 的根节点是 3。
• 因为 rank[2] == rank[3]，将 3 的父节点设置为 2，并增加 rank[2]。

parent = [0, 0, 2, 2, 4]
rank = [2, 1, 2, 1, 1]

操作 3：合并 1 和 3

union(1, 3)

• 找到 1 的根节点是 0，3 的根节点是 2。
• 因为 rank[0] == rank[2]，将 2 的父节点设置为 0，并增加 rank[0]。

parent = [0, 0, 0, 2, 4]
rank = [3, 1, 2, 1, 1]

操作 4：查找 3 的根节点

find(3)

• 从 3 开始，找到父节点 2。
• 从 2 开始，找到父节点 0。
• 返回根节点 0，并进行路径压缩，将 3 的父节点直接设置为 0。

parent = [0, 0, 0, 0, 4]
rank = [3, 1, 2, 1, 1]

---

总结

这段代码是一个标准的并查集实现，包含了路径压缩和按秩合并两种优化。通过逐行讲解和示例演示，希望你能够彻底理解并查集的工作原理和代码实现！如果还有疑问，欢迎继续提问！

990.等式方程的可能性

好的！我会从头开始详细解释并查集（Union-Find）数据结构，并结合这道题目的具体解法，帮助你彻底理解并查集以及如何用它解决这类问题。

---

什么是并查集？

并查集（Union-Find）是一种用于管理不相交集合的数据结构。它支持以下两种核心操作：

1. 查找（Find）：查找某个元素所属的集合（通常用集合的“代表元素”表示）。
2. 合并（Union）：将两个集合合并为一个集合。

并查集常用于解决动态连通性问题，比如判断两个元素是否属于同一个集合，或者将两个集合合并。

---

并查集的核心思想

1. 集合的表示：

   • 每个集合用一棵树表示，树的根节点是集合的“代表元素”。
   • 每个节点都有一个父节点，根节点的父节点是它自己。

2. 查找操作（Find）：

   • 从某个节点出发，沿着父节点向上查找，直到找到根节点。
   • 为了提高效率，可以使用路径压缩：在查找过程中，将路径上的所有节点直接连接到根节点。

3. 合并操作（Union）：

   • 找到两个元素所在集合的根节点。
   • 将其中一个根节点的父节点设置为另一个根节点。
   • 为了提高效率，可以使用按秩合并：将较小的树合并到较大的树上，以保持树的平衡。

---

并查集在本题中的应用

题目分析

题目给出了一组等式和不等式，要求判断是否存在一种赋值方式，使得所有等式和不等式都成立。例如：

• 等式 a==b 表示 a 和 b 必须相等。
• 不等式 a!=b 表示 a 和 b 必须不相等。

解题思路

1. 等式处理：

   • 等式 a==b 表示 a 和 b 属于同一个集合。
   • 我们可以用并查集的 union 操作将 a 和 b 合并到同一个集合中。

2. 不等式处理：

   • 不等式 a!=b 表示 a 和 b 必须属于不同的集合。
   • 我们可以用并查集的 find 操作检查 a 和 b 是否在同一个集合中。如果在同一个集合中，则说明矛盾，返回 False。

3. 步骤总结：

   • 初始化并查集，每个字母初始时属于自己单独的集合。
   • 遍历所有等式，将等号两边的字母合并。
   • 遍历所有不等式，检查不等号两边的字母是否在同一个集合中。如果在同一个集合中，则返回 False。
   • 如果所有不等式都满足，则返回 True。

---

代码实现

class UnionFind:def __init__(self, size):self.parent = list(range(size))  # 初始化每个元素的父节点为自己self.rank = [1] * size  # 初始化每个集合的秩为1def find(self, x):# 查找操作，带路径压缩if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]def union(self, x, y):# 合并操作，带按秩合并rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1class Solution:def equationsPossible(self, equations: List[str]) -> bool:# 初始化并查集，26个小写字母uf = UnionFind(26)# 首先处理所有等式，将等号两边的字母合并for eq in equations:if eq[1] == '=':x = ord(eq[0]) - ord('a')  # 将字母映射到0-25y = ord(eq[3]) - ord('a')uf.union(x, y)# 然后处理所有不等式，检查是否矛盾for eq in equations:if eq[1] == '!':x = ord(eq[0]) - ord('a')y = ord(eq[3]) - ord('a')if uf.find(x) == uf.find(y):  # 如果x和y在同一个集合中，则矛盾return Falsereturn True

---

代码逐行解释

1. UnionFind类：

   • parent数组：存储每个节点的父节点。初始时，每个节点的父节点是它自己。
   • rank数组：存储每个集合的秩（树的高度）。初始时，每个集合的秩为1。
   • find方法：查找某个节点的根节点，并在查找过程中进行路径压缩。
   • union方法：合并两个集合，并根据秩的大小决定如何合并。

2. equationsPossible方法：

   • 初始化并查集，26个小写字母对应0到25的索引。
   • 遍历所有等式：
     • 如果是等式（==），将等号两边的字母合并。
   • 遍历所有不等式：
     • 如果是不等式（!=），检查不等号两边的字母是否在同一个集合中。如果在同一个集合中，则返回 False。
   • 如果所有不等式都满足，则返回 True。

---

示例演示

示例 1：

输入：["a==b","b!=a"]

1. 初始化并查集：
   • parent = [0, 1, 2, ..., 25]（每个字母初始时属于自己单独的集合）。
2. 处理等式 a==b：
   • 将 a 和 b 合并，parent[1] = 0（假设 a 的索引是0，b 的索引是1）。
3. 处理不等式 b!=a：
   • 检查 a 和 b 是否在同一个集合中。发现它们在同一个集合中，返回 False。

示例 2：

输入：["b==a","a==b"]

1. 初始化并查集。
2. 处理等式 b==a：
   • 将 a 和 b 合并。
3. 处理等式 a==b：
   • 再次检查 a 和 b，发现它们已经在同一个集合中。
4. 没有不等式，返回 True。

---

总结

• 并查集的核心是查找和合并操作。
• 在本题中，我们通过并查集维护字母之间的等价关系，并通过检查不等式来判断是否存在矛盾。
• 路径压缩和按秩合并是并查集的优化技巧，可以显著提高效率。

测试代码与详解

好的！下面我会为这段代码编写详细的测试代码，并逐步打印出每一步的运行结果。同时，我会结合代码的每一行，详细说明其作用和实现原理。

---

代码的作用与实现原理

1. 并查集（Union-Find）的作用

并查集是一种用于管理不相交集合的数据结构，支持以下两种核心操作：

• 查找（Find）：查找某个元素所属的集合（通常用集合的“代表元素”表示）。
• 合并（Union）：将两个集合合并为一个集合。

在本题中，并查集用于维护变量之间的等价关系：

• 等式 a==b 表示 a 和 b 属于同一个集合。
• 不等式 a!=b 表示 a 和 b 必须属于不同的集合。

2. 代码的实现原理

• 初始化：
  • self.parent：存储每个元素的父节点，初始时每个元素的父节点是它自己。
  • self.rank：存储每个集合的秩（树的高度），初始时为1。
• 查找操作（Find）：
  • 查找某个元素的根节点，并在查找过程中进行路径压缩，将路径上的所有节点直接连接到根节点。
• 合并操作（Union）：
  • 找到两个元素的根节点，将较小的树合并到较大的树上，以保持树的平衡。
• 等式方程的处理：
  • 遍历所有等式，将等号两边的变量合并。
  • 遍历所有不等式，检查不等号两边的变量是否在同一个集合中。如果在同一个集合中，则返回 False。

---

测试代码

class UnionFind:def __init__(self, size):self.parent = list(range(size))  # 初始化每个元素的父节点为自己self.rank = [1] * size  # 初始化每个集合的秩为1def find(self, x):# 查找操作，带路径压缩if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]def union(self, x, y):# 合并操作，带按秩合并rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1class Solution:def equationsPossible(self, equations: List[str]) -> bool:# 初始化并查集，26个小写字母uf = UnionFind(26)# 首先处理所有等式，将等号两边的变量合并print("处理等式：")for eq in equations:if eq[1] == '=':x = ord(eq[0]) - ord('a')y = ord(eq[3]) - ord('a')print(f"合并 {eq[0]} 和 {eq[3]}")uf.union(x, y)print(f"parent: {uf.parent}")print(f"rank: {uf.rank}")print("-----------------------------")# 然后处理所有不等式，检查是否矛盾print("处理不等式：")for eq in equations:if eq[1] == '!':x = ord(eq[0]) - ord('a')y = ord(eq[3]) - ord('a')print(f"检查 {eq[0]} 和 {eq[3]} 是否在同一个集合中")if uf.find(x) == uf.find(y):print(f"矛盾：{eq[0]} 和 {eq[3]} 在同一个集合中")return Falseelse:print(f"无矛盾：{eq[0]} 和 {eq[3]} 不在同一个集合中")print("-----------------------------")return True# 测试代码
def test_equationsPossible():equations = ["a==b", "b!=a"]  # 测试用例solution = Solution()result = solution.equationsPossible(equations)print("最终结果：", result)# 运行测试
test_equationsPossible()

---

代码运行过程与结果

输入

equations = ["a==b", "b!=a"]

运行过程

1. 初始化并查集：

   • parent = [0, 1, 2, ..., 25]（每个字母初始时属于自己单独的集合）。
   • rank = [1, 1, 1, ..., 1]（每个集合的秩为1）。

2. 处理等式 a==b：

   • 将 a 和 b 合并。
   • a 的索引是 0，b 的索引是 1。
   • 合并后，parent = [0, 0, 2, ..., 25]，rank = [2, 1, 1, ..., 1]。

3. 处理不等式 b!=a：

   • 检查 a 和 b 是否在同一个集合中。
   • 发现 a 和 b 在同一个集合中（根节点都是 0），返回 False。

输出

处理等式：
合并 a 和 b
parent: [0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
rank: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
-----------------------------
处理不等式：
检查 b 和 a 是否在同一个集合中
矛盾：b 和 a 在同一个集合中
最终结果： False

---

代码逐行解释

1. UnionFind类

• __init__：
  • 初始化 parent 和 rank，每个元素初始时属于自己单独的集合。
• find：
  • 查找某个元素的根节点，并在查找过程中进行路径压缩。
• union：
  • 合并两个集合，并根据秩的大小决定如何合并。

2. Solution类

• equationsPossible：
  • 初始化并查集，26个小写字母对应0到25的索引。
  • 遍历所有等式，将等号两边的变量合并。
  • 遍历所有不等式，检查不等号两边的变量是否在同一个集合中。如果在同一个集合中，则返回 False。
  • 如果所有不等式都满足，则返回 True。

---

总结

• 并查集的作用：维护变量之间的等价关系，支持高效的查找和合并操作。
• 路径压缩和按秩合并：优化并查集的性能，使得查找和合并操作的时间复杂度接近 O(1)。
• 测试代码的作用：通过打印每一步的运行结果，验证并查集的正确性和性能。