題目

990. Satisfiability of Equality Equations 給定一個字串序列 $equations$，表示變量之間的關係。每個字串 equations[i] 的長度為4，有兩種不同的形式："xi==yi" 或 "xi!=yi"。其中，$x_i$ 和 $y_i$ 是小寫字母（可以相同），表示單個字母的變量名。

如果能夠對變量名分配整數，使得滿足所有給定的等式關係，則返回 $true$；否則返回 $false$。

解題思路

這道題目可以使用不相交集（$DisjointSet$）的策略來解決。我們將相等的變量視為連接的點，並使用DisjointSet來維護它們之間的關係。如果在同一個連接分量中出現了不等關係，則無法滿足所有的等式。

我們可以使用以下步驟來解決問題：

創建一個空的DisjointSet dsu。
遍歷 equations 序列，對於每個等式 equation：
- 如果 equation 的操作符是 ==，則將兩個變量 x 和 y 連接起來。
再次遍歷 equations 序列，對於每個不等式 equation：
- 如果 equation 的操作符是 !=，則獲取兩個變量 x 和 y。
- 如果 x 和 y 在同一個連接分量中，則返回 $false$。
返回 $true$，表示能夠滿足所有等式。

算法

class DisjointSet:
        def __init__(self):
            self.parent = {}

        def find(self, x):
            if x not in self.parent:
                self.parent[x] = x
            elif self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x, y):
            root_x = self.find(x)
            root_y = self.find(y)
            if root_x != root_y:
                self.parent[root_x] = root_y

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        dsu = DisjointSet()

        # Union操作：將相等的變量連接在一起
        for equation in equations:
            x, operator, _, y = equation
            if operator == '=':
                dsu.union(x, y)

        # 檢查不等關係是否與相等關係矛盾
        for equation in equations:
            x, operator, _, y = equation
            if operator == '!':
                if dsu.find(x) == dsu.find(y):
                    return False

        return True