990。SatisfiabilityofEquations来源：LeetCodehttps://leetcode-cn.com/problems/satisfiability-of-equality-equality-equality题目目标给定一个表示变量之间关系的字符串方程数组，每个字符串方程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<=500equations[i].length==4equationsi和equationsi是小写字母。equationsi是'='或'!'equationsi是'='。解题思路：先看例3和例4。在这两个示例中，给出的不同部分是数组中的第二个方程。看例子4，为什么返回的结果是False？["a==b","b!=c","c==a"]例4中，第二个公式b!=c，而上一个公式中的a==c，那么这里将是如果a替换b，第二个公式就变成了a!=c，但是a==c在最后一个公式中成立，显然这里有冲突，所以这里的结果返回False。在上面的例子中，我们也可以看出相等关系是传递性的，所有相等的变量其实都属于同一个集合。但是这里我们不关心传输的距离，只关心是否连通。那么这里可以考虑使用unioncheck来解决这个问题。这里并集搜索集的设计算法如下：先构造并集搜索集，遍历所有方程。每个方程的两个变量属于连通分量，两者合并；这里，所有的不等式都需要重新遍历一遍，因为不等式的两个变量不属于同一个连通分量，这里不能将两者合并，需要分别查找对应的连通分量，这里有两种情况：如果两个变量属于同一个连通分量，则与原假设不一致，存在矛盾，此处应返回False；如果没有上面提到的矛盾，那么最后会返回True。这里，我们可以把数组中方程的变量看成节点，等式关系代表两个节点的边。上面解释了相等的变量属于同一个连通分量，那么使用联合查找来维护这种关系的具体实现：创建一个数组来存储每个变量的连通分量，每个元素代表连通分量的父节点信息.如果父节点是它自己，那么这就是连通分量的根节点。初始化时，将变量的父节点指向自身。查找操作：从当前变量的父节点向上查找，直到找到根节点；合并操作：将一个变量的根节点指向另一个变量的根节点。具体代码实现如下。输入importListclass解决方案的代码实现：#UnionFind(object):def__init__(self):'''Initializearray'''self.parent=list(range(26))deffind(self,index):'''查询操作查询到根节点这里使用路径压缩'''#如果父节点是自己，那么就是根节点，returnwhileindex!=self.parent[index]:self.parent[index]=self.parent[self.parent[index]]index=self.parent[index]returnindexdefunion(self,index1,index2):'''合并操作将一个变量的根节点指向另一个变量的根节点'''root_index1=self.find(index1)root_index2=self.find(index2)self.parent[root_index1]=root_index2defis_connected(self,index1,index2):'''判断是否连接'''returnself.找到（索引1）==自我。find(index2)defequationsPossible(self,equations:List[str])->bool:uf=Solution.UnionFind()#第一次遍历所有方程，并合并为方程中的方程：ifequation[1]=="=":#这里将可变字符转换为整数#ord('a')返回对应的十进制整数index1=ord(equation[0])-ord('a')index2=ord(equation[3])-ord('a')uf.union(index1,index2)#再次遍历所有不等式,找到方程中方程对应的连通分量：ifequation[1]=='!':index1=ord(equation[0])-ord('a')index2=ord(equation[3])-ord('a')#如果两个变量属于同一个连通分量，则有矛盾，返回Falseifuf.is_connected(index1,index2):returnFalse#最后没有矛盾，返回TruereturnTrue#equations=["b==a","a==b"]equations=["a==b","b!=a"]solution=Solution()solution.equationsPossible(equations)实现结果总结通过例子中这个问题，我们知道方程是传递的，但问题只关心关于连通性，而不是传输距离，所以我们考虑使用联合搜索的思想来解决问题。关于并集搜索集的算法设计过程：首先构造并集搜索集，先遍历所有方程，因为这里的两个变量属于同一个连通分量，然后合并，再次遍历所有不等式，这里的两个变量是平行的如果不属于同一个连通分量，那么就不能合并，必须分别找对应的连通分量。如果此时两个变量的连通分量相同，则与前面的假设不一致，矛盾就产生了。如果上述矛盾均未发生，则返回False，然后返回True。以上就是关于解决《990. 等式方程的可满足性》问题的主要内容。如果觉得文笔还不错，欢迎关注。微信公众号《书所集录》同步更新，也欢迎大家关注。
