离线联系人分组、设备关联和图片聚类，常需要回答“两个对象是否属于同一组”。如果连接只增加、不删除，并查集比反复遍历全部关系更适合；如果还要解释连接路径或频繁撤销连接，应保留原始图，选择图遍历或专门的动态结构。把这段纯 Swift 逻辑放到云端 Mac 的构建前检查中，可以先发现分组错误，再进入耗时的应用构建。
先定义输入与可观察结果
本文使用无向连接，节点编号固定为 0..<n。业务层先把稳定标识映射成整数，不能使用数组中的当前显示位置，否则列表重排就会改变对象身份。映射与连接数据应来自同一份快照。
验收只观察三件事：两点是否连通、剩余组件数量、某点所在组件的大小。重复连接和自环都不能减少组件数；只有原本不连通的两组成功合并，计数才减一。
根节点只是实现细节，不是业务分组编号。同一组连接换个输入顺序，代表元可能改变，但连通关系必须保持一致。
非法索引应在导入层拒绝，并记录行号或记录标识。下面的实现用前置条件表达内部约束，不把静默忽略错误输入当作容错。
写一个可独立运行的实现
将以下内容保存为 union_find_check.swift。按大小合并把小树挂到大树，路径压缩让查询经过的节点直接指向根。大小只在根上有效，不能直接读取任意位置的 sizes。
struct UnionFind {
private var parent: [Int]
private var sizes: [Int]
private(set) var components: Int
init(_ count: Int) {
precondition(count >= 0)
parent = Array(0..<count)
sizes = Array(repeating: 1, count: count)
components = count
}
mutating func root(_ node: Int) -> Int {
precondition(parent.indices.contains(node))
var r = node
while parent[r] != r {
r = parent[r]
}
var current = node
while parent[current] != current {
let next = parent[current]
parent[current] = r
current = next
}
return r
}
@discardableResult
mutating func union(_ a: Int, _ b: Int) -> Bool {
var ra = root(a)
var rb = root(b)
guard ra != rb else { return false }
if sizes[ra] < sizes[rb] {
swap(&ra, &rb)
}
parent[rb] = ra
sizes[ra] += sizes[rb]
components -= 1
return true
}
mutating func connected(_ a: Int, _ b: Int) -> Bool {
let ra = root(a)
let rb = root(b)
return ra == rb
}
mutating func size(of node: Int) -> Int {
let r = root(node)
return sizes[r]
}
}
查询会改写路径，因此方法标记为 mutating。不要把同一个实例直接交给多个并发任务修改；可把一次分组计算放在单个任务内，完成后输出不可变结果。若用 actor 包装，也应让一批连接在不跨越挂起点的操作中完成。
用图遍历交叉核对每次合并
只写几个预期根编号，容易让测试和实现共享同一种错误。更可靠的参照是邻接表遍历：它不使用父指针，也不依赖合并策略。把下面代码接在同一个文件末尾，逐次加入连接并核对全部节点对。
func reachable(_ start: Int, in graph: [[Int]]) -> Set<Int> {
var seen: Set<Int> = [start]
var stack = [start]
while let node = stack.popLast() {
for next in graph[node] {
if seen.insert(next).inserted {
stack.append(next)
}
}
}
return seen
}
func verify(_ edges: [(Int, Int)], count: Int) {
var uf = UnionFind(count)
var graph = Array(repeating: [Int](), count: count)
for (a, b) in edges {
let expectedMerge = !reachable(a, in: graph).contains(b)
precondition(uf.union(a, b) == expectedMerge)
graph[a].append(b)
graph[b].append(a)
var unseen = Set(0..<count)
var expectedComponents = 0
for node in 0..<count {
let group = reachable(node, in: graph)
if unseen.contains(node) {
expectedComponents += 1
unseen.subtract(group)
}
precondition(uf.size(of: node) == group.count)
for other in 0..<count {
precondition(
uf.connected(node, other) == group.contains(other)
)
}
}
precondition(uf.components == expectedComponents)
}
}
let edges = [(0, 1), (2, 3), (1, 2), (0, 3), (4, 4)]
verify(edges, count: 6)
verify(Array(edges.reversed()), count: 6)
precondition(UnionFind(0).components == 0)
这里同时覆盖了跨组合并、重复连接、孤立节点和自环。反序执行不是要求中间状态相同，而是要求每一步都符合当时的图。最终划分还应对输入顺序不敏感。
小规模数据适合逐步全量核对；大规模数据则先在小图上穷举边子集，再做固定种子的抽样。失败时保存完整边序列，不能只保存随机种子，因为生成器或生成规则也可能变化。
接入构建前检查并区分正确性与性能
先确认节点已安装所需工具链，再在脚本所在目录执行：
set -eu
xcrun swift --version
xcrun swift union_find_check.swift
脚本正常结束即通过，前置条件失败会返回非零状态。将脚本与测试数据提交到仓库，让流水线直接使用退出状态，不必解析本地化输出。不要用会删除前置条件检查的 -Ounchecked 编译该验收程序。
路径压缩如何单独验收
连通性正确不能证明路径压缩已经生效。可在测试专用构建中增加只读深度检查：先构造多层树，查询某个深层节点，再确认它直接指向根。不要为了测试向业务接口开放可写父数组。
性能检查另用较大输入，分别记录首次查询与重复查询。不要让全量图遍历参照参与计时，也不要用某次云端运行的毫秒值作为所有机器的硬阈值；更稳定的检查是比较父指针访问次数。
把失败定位到明确边界
组件数异常通常来自重复合并仍然减一；组件大小偏大，先查自环和重复边；合并后部分节点仍不连通，则检查是否错误地修改了输入节点而不是根的父指针。针对每种故障保留一个最小边序列，比留下大批业务数据更容易回归。
输入层另测负数、等于节点总数的编号和未登记标识，确认它们在进入结构前就被拒绝。空集合不允许查询节点，但应正常报告零个组件。
最后明确删除边界：路径压缩会丢掉原始连接形状，不能靠修改一个父指针实现“解除关系”。连接量不大时从剩余边重建最简单；需要回滚时应采用带变更日志的独立设计，并重新评估路径压缩策略。验收通过的标准，是有效输入得到正确划分，无效输入明确失败，超出能力的操作不会被伪装成成功。
常见问题
能否通过根节点编号判断分组结果正确？
不能。根节点由合并顺序和策略决定，应比较任意两点是否连通、组件数量及组件大小，不应固定断言根编号。
删除一条边后可以直接修改 parent 数组吗？
不可以。parent 数组不是原始边集合。静态数据可删除原始边后重新构建；频繁撤销需要单独设计可回滚结构。