难度：★★★☆☆
类型：字符串
方法：并查集

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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] 是 '='

解答

像这一类问题，对象与对象（这里的对象就是题目中所说的变量）之间是通过等号做连接的，真正决定函数的返回值是True还是False的，是不等号。我们将通过等号连接起来的两个变量看做一个连通域，就会构成一张图，图中的每个结点就是变量，边就是相等关系，通过相等关系建立结点与结点的连接（这个抽象的能力是需要有的），连接具有传递性，如果A与B联通，B与C联通，则A与C联通，他们都构成一个连通域。

遍历每个不等式，如果不等式两边的变量在同一个连通域，则方程组一定不成立。而判断两个结点是否在图中同一个连通域，最快捷的办法就是并查集。

并查集已经有成熟的范式可以遵循，包含下面几个函数：

初始化：将所有对象以字典形式保存，并初始化各自的祖先结点为自身；
寻找祖先结点find：通过递归的方式寻找；
构建连接union：将两个结点的祖先结点建立连接，实际上沟通了两个连通域；
判断是否在同一个连通域connect：如果两个结点在同一个连通域，则返回True，否则返回False，根据祖先结点是否是同一个就可以判断。

class UFS:

    def __init__(self, objs):
        self.parent = {_: _ for _ in objs}
        self.count = len(objs)

    def find(self, node):
        if node != self.parent[node]:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        if not self.connect(node1, node2):
            self.parent[self.find(node1)] = self.find(node2)
            self.count -= 1

    def connect(self, node1, node2):
        return self.find(node1) == self.find(node2)


class Solution:
    def equationsPossible(self, equations):

        equal = [eq.split("==") for eq in equations if "==" in eq]
        unequal = [eq.split("!=") for eq in equations if "!=" in eq]
        ufs = UFS(list(set(sum(equal+unequal, []))))

        for m, n in equal:
            ufs.union(m, n)

        for m, n in unequal:
            if ufs.connect(m, n):
                return False
        return True


s = Solution()
print(s.equationsPossible(["a==b","b!=a"]))
print(s.equationsPossible(["b==a","a==b"]))
print(s.equationsPossible(["a==b","b==c","a==c"]))
print(s.equationsPossible(["a==b", "b!=c", "c==a"]))
print(s.equationsPossible(["c==c","b==d","x!=z"]))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析