数据结构其二 并查集

并查集的基本概念

并查集是一种用于管理元素所属集合的数据结构，支持两种操作：

• 查找（Find）：确定元素属于哪个集合
• 合并（Union）：将两个集合合并为一个

并查集的实现

class UnionFind {
  constructor(n) {
    this.parent = Array(n).fill().map((_, i) => i);
    this.rank = Array(n).fill(0);
  }
  
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 路径压缩
    }
    return this.parent[x];
  }
  
  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    
    if (rootX === rootY) return;
    
    // 按秩合并
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
  }
}
      

并查集的应用

并查集可以应用于：

• 判断图中是否有环
• 最小生成树算法（Kruskal算法）
• 网络连接问题
• 等价类划分