给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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 <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 '='，要么是 '!'
equations[i][2] 是 '='
题解：# 【模板题】并查集（Python3）
关于并查集的题目不少，官方给的数据是30道（截止2020-02-20），但是有一些题目虽然官方没有贴`并查集`标签，但是使用并查集来说确非常简单。这类题目如果掌握模板，那么刷这种题会非常快，并且犯错的概率会大大降低，这就是模板的好处。
我这里总结了几道并查集的题目：
- [547.朋友圈](https://leetcode-cn.com/problems/friend-circles/solution/mo-ban-ti-bing-cha-ji-python3-by-fe-lucifer-2/)
- [721. 账户合并](https://leetcode-cn.com/problems/accounts-merge/solution/mo-ban-ti-bing-cha-ji-python3-by-fe-lucifer-3/)
## 思路
并查集有一个重要的特征就是传导性，即A和B是连通的，B和C是连通的，那么A和C就是连通的。 是不是感觉和题目有点像？
题目中的 == 也一样具体传导性，因此我们的想法是基于 == 去 union 两个元素。 如果两个元素是连通的，并且 equation是 != 那么我们返回False，其他情况返回True
为了简单更加清晰，我将并查集模板代码单尽量独拿出来。
## 代码
find union connected 都是典型的模板代码。 然而我并没做计算连通分量，因此这道题根本不需要。 懂的同学可能也发现了，我没有做路径压缩，这直接导致find union connected 的时间复杂度最差的情况退化到$O(N)$。
当然优化也不难，我们只需要给每一个顶层元素设置一个size用来表示连通分量的大小，这样union的时候我们将小的拼接到大的上即可。 另外find的时候我们甚至可以路径压缩，将树高限定到常数，这样时间复杂度可以降低到$O(1)$。
```python
class UF:
parent = {}
def __init__(self, equations):
for eq in equations:
self.parent[eq[0]] = eq[0]
self.parent[eq[3]] = eq[3]
def find(self, x):
while x != self.parent[x]:
x = self.parent[x]
return x
def union(self, p, q):
if self.connected(p, q): return
self.parent[self.find(p)] = self.find(q)
def connected(self, p, q):
return self.find(p) == self.find(q)
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
uf = UF(equations)
for eq in equations:
if eq[1] == '=':
uf.union(eq[0], eq[3])
for eq in equations:
if eq[1] == '!' and uf.connected(eq[0], eq[3]):
return False
return True
```
**复杂度分析**
- 时间复杂度：平均 $O(logN)$，最坏的情况是 O(N)$
- 空间复杂度：我们使用了 parent， 因此空间复杂度为 $O(N)$
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解
LeetCode题解计算机为什么是基于二进制的？可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈
LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924
LeetCode题解微信红包微信红包 如何分配 让每个人在数学期望上是一样的？在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。