UnionFind

并查集（不相交集合），高效处理集合合并和查询。

函数签名

function createUnionFind(size: number): UnionFind

interface UnionFind {
  find(x: number): number
  union(x: number, y: number): boolean
  connected(x: number, y: number): boolean
  count(): number
  getSize(x: number): number
}

API 说明

union(x, y): boolean

合并两个元素所属的集合。

时间复杂度：接近 O(1)

connected(x, y): boolean

判断两个元素是否在同一集合。

时间复杂度：接近 O(1)

使用示例

import { createUnionFind } from '@shared/functions/data-structures/UnionFind'

const uf = createUnionFind(10)

uf.union(0, 1)
uf.union(1, 2)

console.log(uf.connected(0, 2))  // true
console.log(uf.count())          // 8

应用场景

1. 网络连通性：判断网络是否连通
2. 最小生成树：Kruskal 算法
3. 图像处理：连通区域标记
4. 社交网络：朋友圈划分