等式方程的可满足性

990. 等式方程的可满足性 (opens new window)

难度中等45收藏分享切换为英文关注反馈

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

自己先思考了下解题思路，本想着遍历一遍，相等的赋值，不相等的给个不通的值，遇到定义过的就看等式成不成立，但是发现这个思路有很多漏洞，思考无果后去看了题解，首先看到的就是并查集，因为之前没有遇到过并查集的问题，所以先去查看了下并查集的概念

以下摘自百度百科

概念

并查集，在一些有N个元素的集合 (opens new window)应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度 (opens new window)也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合 (opens new window)（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

主要操作

初始化

把每个点所在集合 (opens new window)初始化为其自身。

通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度 (opens new window)均为O(N)。

查找

查找元素所在的集合，即根节点。

合并

将两个元素所在的集合合并为一个集合。

通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

​ 在粗略了解了并查集的概念后，再来思考这道题的解法：

先遍历等式，把相等的构成一个集合，再去遍历不等式，不相等的必定不在一个集合内，检查对应的集合是否在一个集合，就可得出结果

例如

["a==b","b==c","a==c"]
构成的并查集就是：[[a,b,c]],都是等式必然为true
["a==b","b!=c","c==a"]
构成的并查集是：[[a,b,c]]，检查不等式b!=c,但是b,c在一个集合，所以不等式不成立，结构为false

这样第一版就出来了

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function (equations) {
  let unifind = new Unifind()
  for (let j = 0; j < equations.length; j++) {
    if (!equations[j].includes('!')) {
      let split = equations[j].split('==')
      let a = split[0]
      let b = split[1]
      unifind.uni(a,b)
    }
  }
  for (let j = 0; j < equations.length; j++) {
    if (equations[j].includes('!')) {
      let split = equations[j].split('!=')
      let a = split[0]
      let b = split[1]
      if(a===b) return false
      let seta = unifind.find(a)
      let setb = unifind.find(b)
      if(seta===setb&&seta!==false) return false
    }
  }
  return true
};
//定义并查集，并定义初始化操作
function Unifind() {
  this.sets = new Set()
}
//合并集合操作
Unifind.prototype.uni = function (a,b) {
  let seta = this.find(a)||new Set().add(a)
  let setb = this.find(b)||new Set().add(b)
  if(seta!==setb){
    for (let elem of setb) {
      seta.add(elem);
    }
    this.sets.delete(setb)
    this.sets.add(seta)
  }
}
//查找操作
Unifind.prototype.find = function (a) {
  let sets = this.sets
  for (let s of sets) {
    if (s.has(a)) {
      return s
    }
  }
  return false
}

但是运行时间不太理想，所以优化后：

优化过程中对并查集的加深了解：https://blog.csdn.net/liujian20150808/article/details/50848646

通过路径压缩来优化运行速度

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function (equations) {
  let len = equations.length,
    parent = [],
    cnt = [];
    // 26个字母
  for (let i = 0; i < 26; i++) {
    parent[i] = i;
    cnt[i] = 1;
  }

  let find = function (x) {
    while (parent[x] != x) {
      // 进行路径压缩
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  let union = function (a, b) {
    let pa = find(a),
      pb = find(b);
    if (pa == pb) {
      return;
    }
    if (cnt[a] > cnt[b]) {
      parent[pb] = pa;
      cnt[b] += cnt[a];
    } else {
      parent[pa] = pb;
      cnt[a] += cnt[b];
    }
  }
  for (let i = 0; i < len; i++) {
    if (equations[i].indexOf('==') != -1) {
      // 第几个字母
      union(equations[i][0].charCodeAt() - 97, equations[i][3].charCodeAt() - 97);
    }
  }
  for (let i = 0; i < len; i++) {
    if (equations[i].indexOf('==') == -1) {
      let t1 = equations[i][0].charCodeAt() - 97,
        t2 = equations[i][3].charCodeAt() - 97;
      if (find(t1) == find(t2)) {
        return false;
      }
    }
  }
  return true;
};