【并查集】

news/2025/2/3 2:40:05 标签: python

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

并查集的基础知识

  1. 基本概念：

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

  2. 核心思想：

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

  3. 时间复杂度：

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

Python实现

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

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

    def 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] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.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. 动态调整：

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

秩与路径压缩的关系

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

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

代码示例

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

    def 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] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

总结

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

代码解释

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

应用场景

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

并查集代码详细解释

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

代码逐行讲解

1. 初始化部分
python">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）
python">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）
python">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] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.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)。

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

完整的并查集模板代码

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

    def 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] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

    def is_connected(self, x, y):
        # 判断两个元素是否在同一个集合中
        return self.find(x) == self.find(y)

测试代码

python"># 测试并查集功能
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，初始时每个元素是一个独立的集合。

初始化
python">parent = [0, 1, 2, 3, 4]
rank = [1, 1, 1, 1, 1]
操作 1：合并 0 和 1
python">union(0, 1)
  • 找到 0 的根节点是 0，1 的根节点是 1。
  • 因为 rank[0] == rank[1]，将 1 的父节点设置为 0，并增加 rank[0]。
python">parent = [0, 0, 2, 3, 4]
rank = [2, 1, 1, 1, 1]
操作 2：合并 2 和 3
python">union(2, 3)
  • 找到 2 的根节点是 2，3 的根节点是 3。
  • 因为 rank[2] == rank[3]，将 3 的父节点设置为 2，并增加 rank[2]。
python">parent = [0, 0, 2, 2, 4]
rank = [2, 1, 2, 1, 1]
操作 3：合并 1 和 3
python">union(1, 3)
  • 找到 1 的根节点是 0，3 的根节点是 2。
  • 因为 rank[0] == rank[2]，将 2 的父节点设置为 0，并增加 rank[0]。
python">parent = [0, 0, 0, 2, 4]
rank = [3, 1, 2, 1, 1]
操作 4：查找 3 的根节点
python">find(3)
  • 从 3 开始，找到父节点 2。
  • 从 2 开始，找到父节点 0。
  • 返回根节点 0，并进行路径压缩，将 3 的父节点直接设置为 0。
python">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。

代码实现

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

    def 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] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

class 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-25
                y = 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 False
        
        return 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。

测试代码

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

    def 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] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

class 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 False
                else:
                    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()

代码运行过程与结果

输入
python">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)。
  • 测试代码的作用：通过打印每一步的运行结果，验证并查集的正确性和性能。

http://www.niftyadmin.cn/n/5840439.html

相关文章

【大模型LLM面试合集】大语言模型架构_MHA_MQA_GQA

【大模型LLM面试合集】大语言模型架构_MHA_MQA_GQA

MHA_MQA_GQA 1.总结 在 MHA&#xff08;Multi Head Attention&#xff09; 中&#xff0c;每个头有自己单独的 key-value 对&#xff1b;标准的多头注意力机制&#xff0c;h个Query、Key 和 Value 矩阵。在 MQA&#xff08;Multi Query Attention&#xff09; 中只会有一组 k…
阅读更多...
【Vaadin flow 实战】第5讲-使用常用UI组件绘制页面元素

【Vaadin flow 实战】第5讲-使用常用UI组件绘制页面元素

vaadin flow官方提供的UI组件文档地址是 https://vaadin.com/docs/latest/components这里&#xff0c;我简单实战了官方提供的一些免费的UI组件&#xff0c;使用案例如下&#xff1a; Accordion 手风琴 Accordion 手风琴效果组件 Accordion 手风琴-测试案例代码 Slf4j PageT…
阅读更多...
JavaScript系列（51）--解释器实现详解

JavaScript系列（51）--解释器实现详解

JavaScript解释器实现详解 &#x1f3af; 今天&#xff0c;让我们深入探讨JavaScript解释器的实现。解释器是一个将源代码直接转换为结果的程序&#xff0c;通过理解其工作原理&#xff0c;我们可以更好地理解JavaScript的执行过程。 解释器基础概念 &#x1f31f; &#x1f…
阅读更多...
51单片机CLD1602显示万年历+闹钟+农历+整点报时

51单片机CLD1602显示万年历+闹钟+农历+整点报时

1. 硬件设计 硬件是我自己设计的一个通用的51单片机开发平台&#xff0c;可以根据需要自行焊接模块&#xff0c;这是用立创EDA画的一个双层PCB板&#xff0c;所以模块都是插针式&#xff0c;不是表贴的。电路原理图在文末的链接里&#xff0c;PCB图暂时不选择开源。 B站上传的…
阅读更多...
使用 Docker(Podman) 部署 MongoDB 数据库及使用详解

使用 Docker(Podman) 部署 MongoDB 数据库及使用详解

在现代开发环境中&#xff0c;容器化技术&#xff08;如 Docker 和 Podman&#xff09;已成为部署和管理应用程序的标准方式。本文将详细介绍如何使用 Podman/Docker 部署 MongoDB 数据库&#xff0c;并确保其他应用程序容器能够通过 Docker 网络成功连接到 MongoDB。我们将逐步…
阅读更多...
深度学习 Pytorch 神经网络的学习

深度学习 Pytorch 神经网络的学习

本节将从梯度下降法向外拓展&#xff0c;介绍更常用的优化算法&#xff0c;实现神经网络的学习和迭代。在本节课结束将完整实现一个神经网络训练的全流程。 对于像神经网络这样的复杂模型&#xff0c;可能会有数百个 w w w的存在&#xff0c;同时如果我们使用的是像交叉熵这样…
阅读更多...
【竞技宝】裂变天地S1:BB0-2PARI淘汰出局

【竞技宝】裂变天地S1:BB0-2PARI淘汰出局

北京时间2月1日,DOTA2裂变天地S1继续进行,昨日共进行三场比赛,第三场比赛迎来败者组第二轮PARI对阵BB。以下是本场比赛的详细战报。 第一局: 首局比赛,BB在天辉方,PARI在夜魇方。阵容方面,BB点出了圣堂、卡尔、玛尔斯、奶绿、亚巴顿,PARI则是拿到小娜迦、凤凰、大圣、玛西、萨…
阅读更多...
大模型概述（方便不懂技术的人入门）

大模型概述（方便不懂技术的人入门）

1 大模型的价值 LLM模型对人类的作用&#xff0c;就是一个百科全书级的助手。有多么地百科全书&#xff0c;则用参数的量来描述&#xff0c; 一般地&#xff0c;大模型的参数越多&#xff0c;则该模型越好。例如&#xff0c;GPT-3有1750亿个参数&#xff0c;GPT-4可能有超过1万…
阅读更多...
最新文章

Copyright @ 2022~2023