DSU

释义 Definition

DSU 常指 Disjoint Set Union，即“不相交集合并”数据结构（也常叫 Union-Find / 并查集），用于维护若干集合的合并与查询元素所属集合（连通性）等操作。在不同语境中也可能表示其他缩写，但算法与竞赛编程里最常见的是此义。

发音 Pronunciation (IPA)

/ˌdiː ɛs ˈjuː/

例句 Examples

I used DSU to check whether two nodes are connected.
我用 DSU 来检查两个节点是否连通。

With path compression and union by rank, a DSU can handle millions of union and find operations efficiently in Kruskal’s algorithm.
配合路径压缩与按秩合并，DSU 能在 Kruskal 算法中高效处理数百万次合并与查找操作。

词源 Etymology

DSU 是 Disjoint Set Union 的首字母缩写：disjoint（互不重叠的）+ set（集合）+ union（合并）。在算法领域，它用来表示对“互不相交的集合”进行“合并（union）”与“查找（find）”的一类经典数据结构。

相关词 Related Words

• Union-Find
• Disjoint
• Set
• Union
• Find
• Connectivity
• Graph
• Kruskal
• Path Compression
• Rank

文学与著作 Literary Works

• Introduction to Algorithms（CLRS，《算法导论》）：以 “disjoint-set data structure” 讲解并查集在最小生成树等问题中的应用。
• Competitive Programming（Steven & Felix Halim）：竞赛常用数据结构章节中常以 DSU/Union-Find 形式出现。
• The Algorithm Design Manual（Steven S. Skiena，《算法设计手册》）：在图算法与数据结构相关部分提及并查集的典型用途。