快速查询实现

快速查询用什么表示集合？

• 表示: 数组 ids, ids[x] 直接存 x 所属集合的编号;
• 初始化: ids[x] = x;
• 查找: O(1), 直接读取 ids[x];

合并为什么是 O(n)？

• 做法: 把 y 所在集合的所有元素编号统一改成 x 的编号;
• 代价: 每次合并都要扫描整个数组, 单次合并 O(n);

class UnionFindQuickFind {
  constructor(n) {
    this.ids = Array.from({ length: n }, (_, i) => i);
  }

  find(x) {
    return this.ids[x];
  }

  union(x, y) {
    const xId = this.find(x);
    const yId = this.find(y);
    if (xId === yId) return false;
    for (let i = 0; i < this.ids.length; i++) {
      if (this.ids[i] === yId) this.ids[i] = xId;
    }
    return true;
  }

  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}

快速查询适合什么场景？

• 优点: 查询是常数时间, 实现最简单;
• 缺点: 合并代价随元素数量线性增长, 频繁合并时不可用;
• 替代: 合并频繁时改用 快速合并与路径压缩;