# LeetCode: 990. 等式方程的可满足性¶

## 1、题目描述¶

输入：["a==b","b!=a"]



输出：["b==a","a==b"]



输入：["a==b","b==c","a==c"]



输入：["a==b","b!=c","c==a"]



输入：["c==c","b==d","x!=z"]



• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] 和 equations[i][3] 是小写字母
• equations[i][1] 要么是 '='，要么是 '!'
• equations[i][2] 是 '='

## 2、解题思路¶

• 并查集

• 将所有相等的变量放到同一个集合中，判断不相等的变量是否在一个集合中

class DFU:
def __init__(self, length):
self.data = list(range(length))

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

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
self.data[xp] = yp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
mapping = {}
count = 0
for e in equations:
if e[0] not in mapping:
mapping[e[0]] = count
count += 1
if e[-1] not in mapping:
mapping[e[-1]] = count
count += 1

d = DFU(len(mapping))

for e in equations:
if e[1] == "=":
d.union(mapping[e[0]], mapping[e[-1]])

for e in equations:
if e[1] == "!":
if d.find(mapping[e[0]]) == d.find(mapping[e[-1]]):
return False
return True