题目：

  1. 给定一个由表示变量之间关系的字符串方程组成的数组，
  2. 每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。
  3. 在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
  5. 只有当可以将整数分配给变量名，
  6. 以便满足所有给定的方程时才返回 true，否则返回 false。 
  8. 示例 1：
  9. 输入：["a==b","b!=a"]
  10. 输出：false
  11. 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
  13. 来源：力扣（LeetCode）
  14. 链接：https://leetcode-cn.com/problems/satisfiability-of-equality-equations
  15. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

5分钟，unionfind 可以copy 模板

  1. class UnionFind:
  2.     def __init__(self,n):
  3.         self.parent = [i for i in range(n)]
  4.         self.rank = [1 for _ in range(n)]
  5.         self.count = n
  7.     def find(self,p):
  8.         while self.parent[p] != self.parent[self.parent[p]]:
  9.             self.parent[p] = self.parent[self.parent[p]]
  10.         return self.parent[p]
  12.     def union(self,p,q):
  13.         i = self.find(p)
  14.         j = self.find(q)
  15.         if i == j:
  16.             return
  17.         if self.rank [i] < self.rank [j]:
  18.             self.parent[i] = j
  19.             self.rank [j] += self.rank [i]
  20.         else:
  21.             self.parent[j] = i
  22.             self.rank [i] += self.rank [j]
  23.         self.count -= 1
  25. class Solution:
  26.     def equationsPossible(self, equations: List[str]) -> bool:
  27.         equa=UnionFind(1050)
  28.         visit={}
  29.         for x, logo, _,y in equations:
  30.             if x not in visit:
  31.                 visit[x]=len(visit)+1
  32.             if y not in visit:
  33.                 visit[y]=len(visit)+1
  34.             if logo=="=":
  35.                 equa.union(visit[x],visit[y])
  36.         for x ,logo,_,y in equations:
  37.             if logo=="!":
  38.                 if equa.find(visit[x])==equa.find(visit[y]):
  39.                     return False
  40.         return True

要点：

1. 不关心union的个数，所以把个数开了个1050

2. 重要的是给出现的字母编号，类似nlp字典的做法。

3. ==合并到一个集合，用！=查询

4. 如果！=在一个集合那就是false

其他：

代码报错：无