并查集（Disjoint Set）

簡介

并查集是一種非常精巧而實用的資料結構，它主要用于處理一些不相交集合的合并問題。一些常見的用途有求連通子圖、求最小生成樹的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

常常在使用中以森林來表示。集就是讓每個元素構成一個單元素的集合，也就是按一定順序将屬于同一組的元素所在的集合合并。

詳細内容可以參考視訊：視訊位址

思路

• 初始化将所有的元素都獨立為一個集合/樹，形成森林
• 循環處理
  • x -> y 組成一個路徑，表示 x y 是一個集合
  • 分别查找 x y 的根節點，并将對應的兩個樹合并

實作

990. 等式方程的可滿足性

以上述題目為例子：

/**
 * 使用數組來表示森林，-1 表示該元素為根節點
 * 例如：
 * [-1, 0, -1, -1] 表示 1 元素的父節點是 0 元素
 * [-1, 0, -1, 1]  表示 1 元素的父節點是 0 元素，3 元素的父節點是 1 元素
 *
 * 初始化全部為 -1
 */
function DisjointSet(num) {
  this.parents = new Array(num).fill(-1);
}

DisjointSet.prototype.getRoot = function getRoot(x) {
  if (-1 === this.parents[x]) return x;
  return this.getRoot(this.parents[x]);
};

DisjointSet.prototype.union = function union(x, y) {
  const xR = this.getRoot(x);
  const yR = this.getRoot(y);
  if (xR !== yR) {
    // 如果不是同一個根節點，将兩個根節點合并，也就是将兩個樹合并
    this.parents[yR] = xR;
  }
};

/**
 * @param {string[]} equations
 * @return {boolean}
 */
function equationsPossible(equations) {
  const noEq = [];
  const ds = new DisjointSet(26);
  equations.forEach((item) => {
    if ("=" === item[1]) {
      // 将所有的 x==y 的元素處理，生成一個集合
      // 将字母轉換為對應的數字 0 - 26
      ds.union(item.charCodeAt(0) - 97, item.charCodeAt(3) - 97);
    } else {
      noEq.push(item);
    }
  });
  // 從不相等的集合中，分别查找 x y 的根節點
  // 如果一緻則表示兩個元素相等，也就是再同一個集合中。
  // 如果找到傳回 false
  // 沒有找到傳回 true
  return !noEq.find(
    (item) =>
      ds.getRoot(item.charCodeAt(0) - 97) ===
      ds.getRoot(item.charCodeAt(3) - 97)
  );
}
           

優化

在 union 函數中，我們合并的時候不能随便合并，因為有可能會出現非常長的一側（不平衡樹），這樣查找節點就會影響效率。是以我們應該盡量生成一個相對平衡的樹。

例如：分别有兩個集合進行合并，如下：

0 3
  45
           

如果随便合并就會出現：3 指向 0

0
3
45
           

其實我們應該這樣合并：0 指向 3

3
045
           

function DisjointSet(num) {
  this.parents = new Array(num).fill(-1);
  // 用來表示目前根節點樹的高度
  this.heights = new Array(num).fill(0);
}

DisjointSet.prototype.getRoot = function getRoot(x) {
  if (-1 === this.parents[x]) return x;
  return this.getRoot(this.parents[x]);
};

DisjointSet.prototype.union = function union(x, y) {
  const xR = this.getRoot(x);
  const yR = this.getRoot(y);
  if (xR !== yR) {
    // 高度低的樹指向高度高的樹
    if (this.heights[xR] >= this.heights[yR]) {
      this.parents[yR] = xR;
      if (this.heights[xR] === this.heights[yR]) {
        // 如果高度一樣，這個時候合并則對應的樹高度加一
        this.heights[xR] += 1;
      }
    } else {
      this.parents[xR] = yR;
    }
  }
};