LeetCode 990. 等式方程的可满足性

题目描述

给定一个由字符串方程组成的数组 equations，每个方程 equations[i] 的长度为 4，采用以下两种形式之一："a==b" 或 "a!=b"。这里的 a 和 b 是小写字母，代表变量。

你需要判断这些方程是否能够同时成立。换句话说，就是为所有变量分配一个数字（或更抽象地说，分配一个“值”），使得所有等号方程成立，同时所有不等号方程也成立。如果可以，返回 true，否则返回 false。

示例 1：
输入：["a==b", "b!=a"]
输出：false
解释：第一个方程要求 a 和 b 相等，但第二个方程要求它们不相等，这不可能同时满足。

示例 2：
输入：["b==a", "a==b"]
输出：true
解释：我们可以分配 a = 1, b = 1，这样两个等式都成立。

示例 3：
输入：["a==b", "b==c", "a==c"]
输出：true

示例 4：
输入：["a==b", "b!=c", "c==a"]
输出：false

示例 5：
输入：["c==c", "b==d", "x!=z"]
输出：true

解题过程

这个问题的核心在于处理变量之间的相等关系。相等关系具有传递性（如果 a == b 且 b == c，那么 a == c）。我们需要一种高效的数据结构来管理这些具有传递性的关系，并将相关的变量分组。并查集（Union-Find） 是解决这类问题的完美工具。

并查集主要用于处理一些不交集的合并及查询问题。它支持两种操作：

1. 查找（Find）：确定某个元素属于哪个子集。这可以用来判断两个元素是否属于同一个子集。
2. 合并（Union）：将两个子集合并成一个集合。

以下是使用并查集解决此问题的详细步骤：

步骤 1：初始化并查集

由于变量是 26 个小写字母，我们可以创建一个长度为 26 的数组 parent 来表示并查集。数组的索引对应字母（例如，索引 0 代表 ‘a’，索引 1 代表 ‘b’，以此类推）。parent[i] 的值表示变量 i 的父节点。

• 初始时，每个变量都是独立的，即每个变量的父节点都是它自己。parent[i] = i。

步骤 2：处理所有相等关系（== 方程）

我们首先遍历方程数组 equations，但只处理等号方程。

• 对于每个等号方程（如 "a==b"），我们找到这两个变量（‘a’ 和 ‘b’）在并查集中对应的索引。
• 然后，我们执行 Union 操作，将这两个变量所在的集合合并起来。这意味着我们认为它们是相等的，并且所有与它们通过相等关系相连的变量都属于同一个集合。

为什么先处理等号？ 因为等号方程定义了变量之间的连通性（等价关系）。我们先根据这些信息构建出变量之间的“相等关系图”。

步骤 3：处理所有不等关系（!= 方程）

在建立了所有相等关系之后，我们再次遍历方程数组，但这次只处理不等号方程。

• 对于每个不等号方程（如 "a!=b"），我们找到这两个变量（‘a’ 和 ‘b’）在并查集中对应的索引。
• 然后，我们对这两个变量执行 Find 操作。这个操作会找到每个变量所在集合的“根”节点（代表元）。
• 关键判断：如果 Find(a) 等于 Find(b)，这意味着在步骤 2 构建的相等关系图中，a 和 b 是连通的，即根据之前的等号方程，a 和 b 必须相等。但这与当前的不等号方程 a != b 矛盾。因此，一旦发现这种情况，我们立即返回 false。
• 如果对于所有的不等号方程，我们都找不到这样的矛盾（即 Find(a) != Find(b)），那么说明所有方程可以同时满足，返回 true。

并查集操作的实现细节

为了使并查集高效，我们通常使用两种优化技术：

1. 路径压缩（Path Compression）：在 Find 操作时，将查找路径上的每个节点都直接连接到根节点上。这可以极大地扁平化树结构，加速后续的查找操作。

   def find(x, parent):
       if parent[x] != x:
           parent[x] = find(parent[x], parent)  # 递归查找根节点，并直接连接
       return parent[x]
   

2. 按秩合并（Union by Rank）：在 Union 操作时，将一棵深度较小的树连接到一棵深度较大的树的根节点上。这可以避免树变得过高，从而保持查找操作的高效。我们通常用一个额外的 rank 数组来记录每个根的秩（近似于树的深度）。

   def union(x, y, parent, rank):
       rootX = find(x, parent)
       rootY = find(y, parent)
       if rootX != rootY:
           # 将秩小的树合并到秩大的树下
           if rank[rootX] < rank[rootY]:
               parent[rootX] = rootY
           elif rank[rootX] > rank[rootY]:
               parent[rootY] = rootX
           else:
               # 秩相等时，任意合并，但被合并的根节点秩要加1
               parent[rootY] = rootX
               rank[rootX] += 1
   

完整逻辑梳理

1. 初始化：创建 parent 和 rank 数组，每个变量自成一集合。
2. 第一遍遍历（构建连通性）：遇到 "a==b"，调用 union(a, b)，将 a 和 b 所在的集合合并。
3. 第二遍遍历（检查矛盾）：遇到 "a!=b"，调用 find(a) 和 find(b)。如果 find(a) == find(b)，则发现矛盾，返回 false。
4. 最终判断：如果所有不等关系检查完毕均无矛盾，返回 true。

通过这种“先建立相等关系，再检查不等关系是否破坏已有关系”的策略，并利用并查集高效管理连通分量，我们可以清晰地解决这个等式方程的可满足性问题。