并查集算法原理与实现详解

ACM 竞赛并查集资料 并查集是一种重要的数据结构，在 ACM 竞赛中广泛应用。它可以解决许多问题，例如查找元素所属的集合、合并两个集合等。 并查集的定义 ---------------- 并查集是一个数据结构，能够维护不相交的集合（disjoint set），并且可以进行两种操作：检索某元素属于哪个集合和合并两个集合。 并查集的森林实现 ------------------- 一般来说，我们用森林的结构实现并查集。在森林中，每棵树代表一个集合。用树根来表示这个集合。合并操作：两个集合 S1、S2 合并，将其中的一个树根作为另一个树根的子树即可。查找操作：对于一个元素 u 的查找，顺着 u 往上找，直到线索到根节点，也就确定了 u 所在的集合。 两个优化 ------------ 启发式合并：在合并集合 S1、S2 的时候，我们让较小的树成为较大的树的子树。这里可以是深度、节点个数等启发函数来比较树的大小。路径压缩：我们在查找完 u 至根节点的路径之后，一般将这条路径上的所有节点的父节点都设为根节点，这样可以大大减少之后的查找次数。 并查集的时间复杂度 ------------------- 可以证明，经过启发式合并和路径压缩之后的并查集，执行 m 次查找的复杂度为 O(mα(m))。其中 α(m) 是 Ackermann 函数的某个反函数，你可以近似的认为它是小于 5 的。所以并查集的单次查找操作的时间复杂度也几乎是常数级的。 例一银河英雄传说（NOI2002） ------------------------- 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 30000 列，每列依次编号为 1,2,…,30000。之后，他把自己的战舰也依次编号为 1,2,…,30000，让第 i 号战舰处于第 i 列（i=1, 2,…,30000），形成“一字长蛇阵”，诱敌深入。这是初始阵形。 当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为 Mij，含义为让第 i 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 j 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 并查集的应用 ---------------- 并查集有很多实际应用，例如： * 查找元素所属的集合 * 合并两个集合 * 检查两个集合是否相交 * 查找某个元素在哪个集合中 并查集是一个非常重要的数据结构，在 ACM 竞赛中广泛应用。它可以解决许多问题，例如查找元素所属的集合、合并两个集合等。