并查集

定义

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

• 合并（Union）：合并两个元素所属集合（合并对应的树）
• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

定义来源：https://oi-wiki.org/ds/dsu/ 链接里包含并查集在C++和python的实现，以下为golang实现方式

实现

type UnionFind struct {
	parent []int //根节点记录数组，下标为子节点，值为根节点下标
	size   []int //子集中数量，可以按需设计，比如改成height
}
//初始化并查集
func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	size := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
		size[i] = 1
	}
	return &UnionFind{parent: parent, size: size}
}
//向并查集放入新关系
func (uf *UnionFind) Union(u, v int) {
	rootX, rootY := uf.Find(u), uf.Find(v)//查找要关联的两个节点的根节点
	if rootX == rootY {
		//一致表明添加过，所以不再重新添加，size也不用更新[^1]
		return
	}
	if uf.size[rootX] < uf.size[rootY] {//不一致并且子节点的根节点大于链接对象根节点的，将该节点的根节点作为共同的根节点，切换关系
		rootX, rootY = rootY, rootX
	}
	uf.parent[rootY] = rootX//绑定链接对象到目标节点的根节点
	uf.size[rootX] += uf.size[rootY] //子集总数合并，特殊场景，其他场景按需设计
}
// 查找i节点的根节点
func (uf *UnionFind) Find(i int) int {
	if uf.parent[i] != i {//存在根节点，递归更新，路径压缩，直接将路径的子节点的父节点指向根节点
		uf.parent[i] = uf.Find(uf.parent[i])
	}
	return uf.parent[i] //返回存储在parent的根节点
}
func (uf *UnionFind) Size(i int) int {
	return uf.size[uf.Find(i)] // 在该场景中，size查询的是节点i所在的子集里节点的总数
}

代码演示

Go 实现

package main

import "fmt"

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	return &UnionFind{parent: parent, rank: rank}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
	px, py := uf.Find(x), uf.Find(y)
	if px == py {
		return false
	}
	if uf.rank[px] < uf.rank[py] {
		px, py = py, px
	}
	uf.parent[py] = px
	if uf.rank[px] == uf.rank[py] {
		uf.rank[px]++
	}
	return true
}

func (uf *UnionFind) Connected(x, y int) bool {
	return uf.Find(x) == uf.Find(y)
}

// 运行示例输出：
//
//	0 and 2 connected: true
//	0 and 3 connected: false
//	3 and 4 connected: true
//	1 and 5 connected: false
//	after union(2,3):
//	0 and 4 connected: true
func main() {
	uf := NewUnionFind(6)

	uf.Union(0, 1)
	uf.Union(1, 2)
	uf.Union(3, 4)

	fmt.Println("0 and 2 connected:", uf.Connected(0, 2)) // true
	fmt.Println("0 and 3 connected:", uf.Connected(0, 3)) // false
	fmt.Println("3 and 4 connected:", uf.Connected(3, 4)) // true
	fmt.Println("1 and 5 connected:", uf.Connected(1, 5)) // false

	uf.Union(2, 3)
	fmt.Println("after union(2,3):")
	fmt.Println("0 and 4 connected:", uf.Connected(0, 4)) // true
}

JS 性能对比

// 并查集性能对比：naive vs. 路径压缩 + 按秩合并

interface UnionFind {
  find: (x: number) => number
  union: (x: number, y: number) => void
}

function makeNaive(n: number): UnionFind {
  const parent = Array.from({ length: n }, (_, i) => i)
  function find(x: number): number {
    while (parent[x] !== x) x = parent[x]
    return x
  }
  function union(x: number, y: number): void {
    parent[find(x)] = find(y)
  }
  return { find, union }
}

function makeOptimized(n: number): UnionFind {
  const parent = Array.from({ length: n }, (_, i) => i)
  const rank = Array.from({ length: n }).fill(0) as number[]
  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]] // path halving
      x = parent[x]
    }
    return x
  }
  function union(x: number, y: number): void {
    const px = find(x)
    const py = find(y)
    if (px === py)
      return
    if (rank[px] < rank[py]) {
      parent[px] = py
    }
    else if (rank[px] > rank[py]) {
      parent[py] = px
    }
    else {
      parent[py] = px
      rank[px]++
    }
  }
  return { find, union }
}

// 简单 LCG 伪随机，保证两次跑相同操作序列
function createRng(seed: number) {
  return () => ((seed = (seed * 1664525 + 1013904223) >>> 0) / 0x100000000)
}

function runBenchmark(
  uf: UnionFind,
  n: number,
  ops: { type: 'union' | 'find', x: number, y?: number }[],
): number {
  const start = performance.now()
  for (const op of ops) {
    if (op.type === 'union')
      uf.union(op.x, op.y!)
    else
      uf.find(op.x)
  }
  return performance.now() - start
}

const N = 50_000
const OP_COUNT = 200_000
const rng = createRng(42)
const ops: { type: 'union' | 'find', x: number, y?: number }[] = []
for (let i = 0; i < OP_COUNT; i++) {
  const type = rng() < 0.3 ? 'union' : 'find'
  const x = (rng() * N) | 0
  const y = (rng() * N) | 0
  ops.push(type === 'union' ? { type: 'union', x, y } : { type: 'find', x })
}

const naiveTime = runBenchmark(makeNaive(N), N, ops)
const optimizedTime = runBenchmark(makeOptimized(N), N, ops)

// 输出性能对比结果（使用 warn 以便在控制台可见）
// 示例输出：
//   n=50,000, 200,000 次操作
//   naive:     1409.34 ms
//   optimized: 5.17 ms
//   加速比:    272.74x
console.warn(`n=${N.toLocaleString()}, ${OP_COUNT.toLocaleString()} 次操作`)
console.warn(`naive:     ${naiveTime.toFixed(2)} ms`)
console.warn(`optimized: ${optimizedTime.toFixed(2)} ms`)
console.warn(`加速比:    ${(naiveTime / optimizedTime).toFixed(2)}x`)