Preface

注释 \(\text{card}\) 是基数，即集合大小。

启发式合并就是将 \(\text{card}\) 较小的集合并入 \(\text{card}\) 较大的集合。

感觉挺暴力，那分析一下每个元素被复制了多少次。

将 \(A\) 并入 \(B\)，\(\forall i \in A\) 被复制一次，其所在的集合的大小至少 \(\times 2\)，所以一个元素最多被复制 \(\log N\) 次，\(N\) 为 \(\text{card}(\)全集\()\)，时间复杂度是 \(O(N\log N)\).

举例：令 \(x\) 在集合 \(\{x\}\) 内，则第一次合并后 \(\text{card}(x)\ge 2\)，第二次合并后 \(\text{card}(x)\ge 4\)，第三次合并后 \(\text{card}(x)\ge 8\)……若干次后 \(\text{card}(x)\le N\)，即 \(2^{合并次数}\le N\).

Content

树上启发式合并

0

FLOJ 4897

code