## [990\. 等式方程的可滿足性](https://leetcode-cn.com/problems/satisfiability-of-equality-equations/) >Medium #### 思路 **首先還是一樣，閱讀理解** 先看等式，`a==b , b==c` 從此，我們可以得到隱藏的條件`a == c`，這時假如數組中有`a != c`，那就是矛盾的。 * 可以想到，我們可以將相等連接的元素即`==`符號鏈接的元素，形成一個樹狀結構 * 這時在樹狀結構的路中，有一個矛盾的內容，也就是`!=`符號連接，那就返回`false` * 組成鏈路，我們想到用并查集方法 * 遍歷兩次數組，一次構建連接樹，一次查找 綜上，AC！ #### 代碼 python3 ``` class Solution: def equationsPossible(self, equations: List[str]) -> bool: class UnionFind(): def __init__(self, equations): self.s = {} for e in equations: self.s[e[0]] = e[0] self.s[e[3]] = e[3] def find(self, x): while x != self.s[x]: x = self.s[x] return x def union(self, a ,b): if self.find(a) != self.find(b): self.s[self.find(a)] = self.find(b) uf = UnionFind(equations) for e in equations: if e[1] != "!": uf.union(e[0], e[3]) for e in equations: if e[1] == "!": if uf.find(e[0]) == uf.find(e[3]): return False return True ```