并查集

原文：并查集从入门到出门 (opens new window)

class UnionFind {
  /**
   * @param {number[]} parent
   */
  constructor(parent) {
    this.parent = parent;
    const n = this.parent.length;
    this.size = new Array(n).fill(1);
    this.rank = new Array(n).fill(1);
  }

  /**
   * 直接查找
   * @param {number} x
   * @returns {number}
   */
  findDirect(x) {
    if (this.parent[x] === x) return x;
    return this.findDirect(this.parent[x]);
  }

  /**
   * 带路径压缩的查找
   * @param {number} x
   * @returns {number}
   */
  find(x) {
    if (this.parent[x] === x) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  /**
   * 直接求并
   * @param {number} x
   * @param {number} y
   */
  unionDirect(x, y) {
    const xRoot = this.find(x);
    const yRoot = this.find(y);
    if (xRoot !== yRoot) {
      this.parent[yRoot] = xRoot;
    }
  }

  /**
   * 按大小求并
   * @param {number} x
   * @param {number} y
   */
  unionBySize(x, y) {
    const xRoot = this.find(x);
    const yRoot = this.find(y);
    if (xRoot !== yRoot) {
      if (this.size[yRoot] <= this.size[xRoot]) {
        this.parent[yRoot] = xRoot;
        this.size[xRoot] += this.size[yRoot];
      } else {
        this.parent[xRoot] = yRoot;
        this.size[yRoot] += this.size[xRoot];
      }
    }
  }

  /**
   * 按秩求并
   * @param {number} x
   * @param {number} y
   */
  unionByRank(x, y) {
    const xRoot = this.find(x);
    const yRoot = this.find(y);
    if (xRoot !== yRoot) {
      if (this.rank[yRoot] <= this.rank[xRoot]) {
        this.parent[yRoot] = xRoot;
      } else {
        this.parent[xRoot] = yRoot;
      }
      if (this.rank[xRoot] === this.rank[yRoot]) {
        this.rank[xRoot]++;
      }
    }
  }
}