Union-Find

定义 Definition

Union-Find（并查集）是一种常用的数据结构，用来维护一组元素的“分组/集合”关系，并高效支持两类核心操作：

• union：把两个集合合并成一个集合
• find：查询某个元素属于哪个集合（通常返回该集合的代表/根）

它常用于判断连通性问题（例如图中两点是否连通），并在加入路径压缩等优化后非常高效。

发音 Pronunciation

/ˈjuːnjən faɪnd/

例句 Examples

Union-find can quickly tell whether two nodes are connected.
并查集可以快速判断两个节点是否连通。

Using union-find with path compression, Kruskal’s algorithm efficiently builds a minimum spanning tree even on large graphs.
在使用路径压缩的并查集时，Kruskal 算法即使面对大型图也能高效构建最小生成树。

词源 Etymology

Union-Find是由两个英文动词组合而成的术语：union（合并）与 find（查找），直接对应并查集的两类基本操作。该结构在算法研究中也常被称为 **disjoint-set (union)**（不相交集合结构），强调各集合彼此不重叠、通过合并逐步变化。

相关词 Related Words

• Algorithm
• Connectivity
• Data Structure
• Disjoint Set
• Graph
• Kruskal
• Minimum Spanning Tree
• Path Compression
• Union By Rank

文学与著作示例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——在讲解不相交集合与图算法（如最小生成树）时使用并查集/union-find。
• Algorithms（Robert Sedgewick, Kevin Wayne）——在动态连通性（dynamic connectivity）与并查集实现中系统介绍 union-find。
• Tarjan, R. E. (1975), Efficiency of a Good But Not Linear Set Union Algorithm ——经典论文之一，分析并查集及其优化（如路径压缩）的效率。