题目

题目来源：力扣（LeetCode）

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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

思路分析

我们可以将每一个变量看作是图中的一个节点，把相等的关系 == 看作是连接两个节点的边。由于表示相等关系的等式方程具有传递性，即如果 a == b 和 b == c 成立，那么 a == c 也成立。也就是说，所有相等的变量属于同一个连通分量。因此，我们可以使用并查集来维护这种连通分量的关系。

我们首先以 26 个英文字母的长度构造一个并查集。
然后是第一次遍历，同一个等式中的变量属于同一个连通分量，因此将两个变量进行合并。即在第一次遍历时，首先遇到的是 “=” ，就将等式两边的变量进行合并。

然后再次遍历所有的字符串方程，在同一个不等式中的两个变量属于不同的连通分量，因此对两个变量分别查找器所在的连同分量，如果不等式中的两个变量在同一个连通分量中，则产生矛盾，返回 false。即在第二次遍历时，遇到 “!” 时，分别查找不等式两边变量各自的祖先，如果两个变量拥有共同的祖先，则返回 false 。

  1. /**
  2.  * @param {string[]} equations
  3.  * @return {boolean}
  4.  */
  5. var equationsPossible = function(equations) {
  6.   // 以 26 个英文字母的长度构造一个并查集
  7.   let uf = new UnionFind(26);
  8.   // 第一次遍历，遇到 "=" ，则将等式两边的变量进行合并
  9.   for (str of equations) {
  10.     // 前端字符不能相减，转下码；97是小写字母a 的ASCII码
  11.     if (str.charAt(1) == '=') {
  12.       //charCodeAt() 方法可返回指定位置的字符的 Unicode 编码。用于考虑26个小写字母；
  13.       uf.unite(str.charCodeAt(0) - 97, str.charCodeAt(3) -97);
  14.     }
  15.   }
  16.   // 第二次遍历，遇到 "!" ，查找不等式两边的变量各自的祖先
  17.   for (str of equations) {
  18.     if (str.charAt(1) == '!') {
  19.       //如果不等式两边的变量拥有共同的祖先，说明等式产生矛盾，返回false。
  20.       if (uf.findSet(str.charCodeAt(0) - 97) == uf.findSet(str.charCodeAt(3) - 97)) {
  21.         return false;
  22.       }
  23.     }
  24.   }
  25.   return true;
  26. };
  28. // 并查集
  29. class UnionFind {
  30.   constructor(n) {
  31.     // 元素所指向的父节点，parent[i] 表示第 i 个元素所指向的父节点
  32.     // 初始化时, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
  33.     this.parent = new Array(n).fill(0).map((value, index) => index);
  34.     // 树的层数，rank[i] 表示以 i 为根的集合所表示的树的层数
  35.     this.rank = new Array(n).fill(1);
  36.     // 节点的个数
  37.     this.setCount = n;
  38.   }
  40.   // 查找过程，查找元素 index 所在集合的编号(查找树的根节点)
  41.   findSet(index) {
  42.     // 不断去查询自己的父节点，直至根节点
  43.     // 根节点的标志是父节点就是本身  parent[index] == index
  44.     if (this.parent[index] != index) {
  45.       // 递归获取节点的父节点
  46.       this.parent[index] = this.findSet(this.parent[index]);
  47.     }
  48.     // 返回根节点
  49.     return this.parent[index];
  50.   }
  52.   // 合并两个集合
  53.   unite(index1, index2) {
  54.     let root1 = this.findSet(index1);
  55.     let root2 = this.findSet(index2);
  56.     // 根节点不一样，是两个不同的集合(两棵不同的树)
  57.     if (root1 != root2) {
  58.       // 根据树的层数合并集合
  59.       // 
  60.       if (this.rank[root1] < this.rank[root2]) {
  61.         // 这个判断如果 root2 所在树的层数 大于 root1，就交换两个父节点，这样始终让 root1 为父节点
  62.         [root1, root2] = [root2, root1];
  63.       }
  64.       // 将层数多的集合合并到集合少的集合
  65.       this.parent[root2] = root1;
  66.       this.rank[root1] += this.rank[root2];
  67.       this.setCount--;
  68.     }
  69.   }
  71.   getCount() {
  72.     return this.setCount;
  73.   }
  75.   connected(index1, index2) {
  76.     let root1 = this.findSet(index1);
  77.     let root2 = this.findSet(index2);
  78.     return root1 == root2;
  79.   }
  80. }