990.等式方程的可满足性

https://leetcode-cn.com/problems/satisfiability-of-equality-equations/

一、并查集

==可以理解为连通性，!=可以理解为非连通。原问题转化为图，用并查集求解

==具有传递性，因此可以将所有等式连成一个连通分量。

然后对所有不等式的两端a、b，用并查集的isConnected方法测试连通性，若所有不等式的a、b不连通，说明方程组可满足；若存在连通性，说明方程组无法满足

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = totalNodes
        # 树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	# 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count
        
class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        notEquals = list()	#存储不等式
        uf = UnionFind(26)	# 用0~25表示a~z，因此并查集一共26个结点
        #处理所有方程
        for equation in equations:   
            node1, node2 = ord(equation[0]) - ord('a'), ord(equation[3]) - ord('a')
            if equation[1] == '=':	#等式，将两端点连通
                uf.union(node1, node2)
            else:	#不等式先记录
                notEquals.append((node1, node2))
        for node1, node2 in notEquals:
            if uf.isConnected(node1, node2):
                return False
        return True