<jupyter_start><jupyter_text>给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。    在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。    只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 示例 1：    输入：["a==b","b!=a"]    输出：false    解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。示例 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提示：    1 <= equations.length <= 500    equations[i].length == 4    equations[i][0] 和 equations[i][3] 是小写字母    equations[i][1] 要么是 '='，要么是 '!'    equations[i][2] 是 '='<jupyter_code>class Solution:
    def equationsPossible(self, equations) -> bool:
        def find(a):
            # 寻找a的祖先
            pass
        
        def merge(a, b):
            # 将a的祖先和b的祖先串在一起
            pass
        pass
from collections import defaultdict

class Solution:
    def equationsPossible(self, equations) -> bool:
        graph = defaultdict(set)
        for i in range(len(equations)):
            if equations[i][1:3] == '==':
                graph[equations[i][0]].add(equations[i][-1])
                graph[equations[i][-1]].add(equations[i][0])
        
        for key, val in graph.items():
            seen = set()
            q = list(val)
            while q:
                n = q.pop()
                if n not in seen:
                    seen.add(n)
                    q.extend(graph[n])
                    graph[key] |= graph[n]
        
        for i in range(len(equations)):
            item = equations[i]
            l, r = item[0], item[-1]
            if item[1:3] == '!=':
                a = l == r
                b = a or r in graph[l]
                c = b or l in graph[r]
                d = c or len((graph[l] & graph[r])) > 0
                if d:
                    return False
        return True
from collections import defaultdict

class Solution:
    def equationsPossible(self, equations) -> bool:
        # 所有相等的归为一类
        def find(x):
            if father[x] != x:
                father[x] = find(father[x])
            return father[x]
        
        def merge(a, b):
            a_f = find(a)
            b_f = find(b)
            if a < b:
                father[b_f] = a_f
            else:
                father[a_f] = b_f
            
        
        father = [x for x in range(26)] # 每个元素都是自己的祖先
        
        for eq in equations:
            if eq[1] == '=':
                l = ord(eq[0]) - ord('a')
                r = ord(eq[-1]) - ord('a')
                if find(l) != find(r):
                    merge(l, r)
                    
        for eq in equations:
            if eq[1] == '!':
                l = ord(eq[0]) - ord('a')
                r = ord(eq[-1]) - ord('a')
                if find(l) == find(r):
                    return False
        return True
solution = Solution()
solution.equationsPossible(["a==b","e==c","b==c","a!=e"])<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup