并查集

https://blog.csdn.net/Antonio915/article/details/142330119

‌ 并查集中的“秩”是指树的高度或深度 ‌。秩是用来表示一个节点在树中的相对高度，通常初始时每个节点的秩被设定为 0。秩的主要作用是优化合并操作，以保持并查集的结构尽可能扁平，从而提高查询效率 ‌

路径压缩 在 find 时使路径上的所有节点都指向根节点，从而降低树的高度

class UnionFind {
  constructor(n) {
    // 初始化父节点数组，每个元素的父节点是自己
    this.parent = new Array(n);
    // 初始化秩数组，用于按秩合并
    this.rank = new Array(n);
    for (let i = 0; i < n; i++) {
      this.parent[i] = i; // 每个元素初始时是自己的父节点
      this.rank[i] = 1; // 初始秩为1
    }
  }

  // 查找操作（带路径压缩）
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 路径压缩 递归地把所有链状整合成平级
    }
    // 如果全等，说明找到代表并集的位置
    return this.parent[x];
  }

  // 合并操作（强行）（带按秩合并）
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      // 按秩合并
      if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX; // 将Y的根节点指向X的根节点
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY; // 将X的根节点指向Y的根节点
      } else {
        this.parent[rootY] = rootX; // 将Y的根节点指向X的根节点
        this.rank[rootX]++; // 增加X的秩
      }
    }
  }

  // 判断两个元素是否在同一个集合
  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}