并查集（UNION-FIND）算法

(opens new window) 归并集基本概念 (opens new window)

用集合中的一个元素代表集合

// 使用js 模拟 UF 过程
class UF {
  constructor(n) {
    this.size = n
    this.parent = new Array(n).fill(0)
    for (let i = 0; i < n; i++) {
      // 将所有的元素父级指向自己
      this.parent[i] = i
    }
  }
  find(x) {
    // 路径压缩 压缩树的高度，
    // while (this.parent[x] !== x) {
    //   x = this.parent[x]
    // }
    // return x
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
  union(p, q) {
    // 将p的父级指向q的父级
    const rootP = this.find(p)
    const rootQ = this.find(q)
    this.parent[rootP] = rootQ
    this.size--
  }
  connected(p, q) {
    const rootP = this.find(p)
    const rootQ = this.find(q)
    return rootP === rootQ
  }

  count() {
    return this.size
  }
}

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

/**
 * @param {string[]} equations
 * @return {boolean}
 */
class UF {
  constructor(n) {
    this.size = n
    this.parent = new Array(n).fill(0)
    for (let i = 0; i < n; i++) {
      // 将所有的元素父级指向自己
      this.parent[i] = i
    }
  }
  find(x) {
    // 路径压缩 压缩树的高度，
    // while (this.parent[x] !== x) {
    //   x = this.parent[x]
    // }
    // return x
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
  union(p, q) {
    // 将p的父级指向q的父级
    const rootP = this.find(p)
    const rootQ = this.find(q)
    if (rootP === rootQ) return
    this.parent[rootP] = rootQ
    this.size--
  }
  connected(p, q) {
    const rootP = this.find(p)
    const rootQ = this.find(q)
    return rootP === rootQ
  }

  count() {
    return this.size
  }
}

var equationsPossible = function (equations) {
  // 26 个英文字母
  const uf = new UF(26)
  for (let s of equations) {
    if (s[1] === '=') {
      uf.union(s[0].charCodeAt() - 'a'.charCodeAt(), s[3].charCodeAt() - 'a'.charCodeAt())
    }
  }

  for (let s of equations) {
    if (s[1] === '!') {
      console.log(uf.connected(s[0].charCodeAt() - 'a'.charCodeAt(), s[3].charCodeAt() - 'a'.charCodeAt()))
      if (uf.connected(s[0].charCodeAt() - 'a'.charCodeAt(), s[3].charCodeAt() - 'a'.charCodeAt())) {
        return false
      }
    }
  }
  return true
}