题目分析

这道题目是一个集合问题，相等的变量位于同一个集合之中，判断不相等的变量是否存在于同一个集合之中，集合之间的查询要想到并查集。

并查集

先将相等关系进行处理，把所有的变量分成不同的集合，最后再遍历不等关系，判断不相等的两个遍历是否存在于同一个集合之中。

class UnionFind:
    def __init__(self, equations):
        self.parents = {}
        for x, _, _, y in equations:
            self.parents[x] = x
            self.parents[y] = y

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

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


class Solution:
    def equationsPossible(self, equations):
        uf = UnionFind(equations)
        for x, c, _, y in equations:
            if c == '=':
                uf.union(x, y)
        for x, c, _, y in equations:
            if c == '!' and uf.find(x) == uf.find(y):
                return False
        return True

刷题总结

此题还可以使用BFS或者DFS求解，类似于岛屿问题，将这些变量分成不同的集合，但是因为还需要判断变量之间的不等号关系，即判断变量之间是否不在同一个集合，如果使用BFS或者DFS还需要将每一组不等号去搜索两个变量是否为同一个集合，而并查集每个元素都有一个老大，因此比较两个老大是否为同一个就可以比较是否在同一个集合中，思路清晰，代码也很简单。