# 并查集

并查集（Union-Find）是一种数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种操作：查找（Find）和合并（Union）。查找操作用于判断两个元素是否在同一个集合中，而合并操作用于将两个集合合并成一个集合。

并查集的时间复杂度通常接近于路径压缩和按秩合并后的最优解，使得单次操作几乎可以达到常数时间。

下面是一个使用 JavaScript 实现的简单并查集示例：

class UnionFind {
  constructor(size) {
    this.parent = new Array(size).fill(0).map((_, i) => i);
    this.rank = new Array(size).fill(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) {
      return; // 已经在同一个集合中
    }

    if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
  }

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

// 示例用法
const uf = new UnionFind(5);

uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);

console.log(uf.isConnected(0, 2)); // true
console.log(uf.isConnected(0, 3)); // false

在这个示例中，我们创建了一个 UnionFind 类，并实现了以下功能：

constructor(size): 初始化并查集，大小为 size。
find(x): 查找元素 x 的根节点，并进行路径压缩。
union(x, y): 合并包含元素 x 和 y 的两个集合。
isConnected(x, y): 判断元素 x 和 y 是否在同一个集合中。

通过这些方法，我们可以高效地处理不相交集合的合并及查询问题。

← 简介