leetcode990. 等式方程的可满足性 并查集

**等式方程的可满足性**

给定一个等式方程 `a1 + a2 + ... + ak = b1 + b2 + ... + bn`，其中 `ai` 和 `bi` 是整数。我们需要判断这个等式是否有解。

**并查集**

为了解决这个问题，我们可以使用并查集（Union-Find）数据结构。并查集是一种用于管理一个集合中元素的关系的数据结构，它支持两个主要操作：`union` 和 `find`。

* `union(a, b)`: 将 `a` 和 `b` 合并为一个集合。
* `find(a)`：返回 `a` 所属的集合。

**解决方案**

我们可以使用并查集来解决这个问题。具体来说，我们可以将每个数字视为一个元素，将等式两边的数字分组到不同的集合中，然后检查是否存在两个集合中的数字之和相等的情况。

class UnionFind:
 def __init__(self, n):
 self.parent = list(range(n))
 self.rank = [0] * n def find(self, x):
 if self.parent[x] != x:
 self.parent[x] = self.find(self.parent[x])
 return self.parent[x]

 def union(self, a, b):
 rootA = self.find(a)
 rootB = self.find(b)

 if rootA != rootB:
 if self.rank[rootA] > self.rank[rootB]:
 self.parent[rootB] = rootA elif self.rank[rootA] < self.rank[rootB]:
 self.parent[rootA] = rootB else:
 self.parent[rootB] = rootA self.rank[rootA] +=1class Solution:
 def equationsPossible(self, equations):
 uf = UnionFind(26)

 for equation in equations:
 if equation[1] == '=':
 uf.union(ord(equation[0]) - ord('a'), ord(equation[3]) - ord('a'))

 for equation in equations:
 if equation[1] != '=' and uf.find(ord(equation[0]) - ord('a')) == uf.find(ord(equation[3]) - ord('a')):
 return False return True