并查集是一种树形的数据结构,它支持两种操作:
我们令 find
函数表示寻找 \(x\) 的祖先。如果 \(x\) 已经是祖先,则返回;否则递归到 \(f[x]\) 的子问题。
int find(int x) { return f[x] == x ? x : find(f[x]); }
但是它在最坏情况下(如一条链)是单次 \(O(n)\) 的。考虑把在路径上的每个节点都直接连接到祖先上,我们称之为路径压缩。
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
我们令 merge
函数表示合并 \(x,y\) 所在的集合。显然可以把 \(x\) 所在集合的祖先与 \(y\) 所在的集合的祖先相连,达到该目的。
void merge(int x, int y) { f[find(x)] = find(y); }
这样合并显得很无脑,我们考虑衡量一个集合的指标:大小和深度。以大小为例,我们将小的往大的合并,那么感性理解 find
函数递归的次数会相对少一些,我们称之为启发式合并。
void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (sz[x] > sz[y]) swap(x, y); f[x] = y, sz[y] += sz[x]; }
我们定义 \(Ack(n,m)\) 表示阿克曼函数,\(\alpha(n)\) 表示反阿克曼函数。容易发现 \(\alpha(n)\) 的增长速度极其缓慢,在 OI 中一般默认它 \(\le 4\),可视为常数。
路径压缩 | 启发式合并 | 期望复杂度 | 最坏复杂度 |
---|---|---|---|
无 | 无 | 单次 \(O(\log n)\) | 单次 \(O(n)\) |
无 | 有 | 单次 \(O(\log n)\) | 单次 \(O(\log n)\) |
有 | 无 | 均摊 \(O(m\alpha(m,n))^{[1]}\) | 均摊 \(O(m\log n)^{[2]}\) |
有 | 有 | 单次 \(O(\log n)\),均摊 \(O(m\alpha(m,n))\) | 单次 \(O(\log n)\),均摊 \(O(m\alpha(m,n))\) |
我们可以在并查集的边上定义某种权值,每个点存的是它到它当前指向的祖先间的权值信息。在路径压缩时,将路径上的点的权值信息依次修改过去即可。
要支持查询历史版本,用主席树维护即可。
此时我们不能再路径压缩了,否则撤销会出大问题。因此只采用启发式合并,复杂度单次 \(O(\log n)\)。
如果我们把加边、删边看成一个进栈、弹栈的过程的话,那么我们每次撤销只能弹栈顶的边(即最近一次加入的边)。
在做传统双指针问题的时候,我们遇到过“双栈结构”的 trick。
它的想法是开两个栈,一个倒的栈,一个正的栈。删头可以直接弹“倒栈”的头,加尾可以直接塞“正栈”的头。遇到“倒栈”为空时,把“正栈”全部弹进“倒栈”,自己变空。
容易发现一个元素只会依次在两个栈中出现,对复杂度的贡献是 \(O(1)\),所以总时间复杂度是 \(O(n)\) 的。
这引发我们的思考:为何传统问题能这样做,而可撤销并查集就不行呢?仔细思考,便会发现它有一大硬伤:它自身有一个加边的栈顺序。在它的眼里,它是将我们的两个栈归并在了一起看的,而每次只能撤销最新一次加入的边,那我们的两个栈就不方便撤销了。
因此,我们被迫顺着可撤销并查集来设计算法,我们用一个 stack
记录两个栈按照加边顺序归并在一起的结果,其中 stack
内每个元素都是三元组 (rev, u, v)
,rev
用来表示它是哪个栈的,\(u,v\) 则表示这条边的两端点。
考虑下面这样一个流程:
stack
的头开始一直删,直到取出的两个栈的元素个数相等。