并查集

这道题本来只需要输出 Y / N。加上「最后输出连通块个数」这一行，是故意的：

★ 第 35 章那条教训（题面多问一句，对拍就多一条腿）在这一章有一个极干净的现场： 第 12 步那个「忘了判已经同族就 cnt--」的 bug， 只看 Y / N 那半是 0 / 300，把最后那一行算上就是 300 / 300。

一行输出，把一个 bug 从「测不到」抬到「第 1 轮就抓住」。

8 12
1 1 2      合并 {1,2}
2 1 3      → N
1 2 3      合并 {1,2,3}
2 1 3      → Y
1 1 3      ★ 它俩已经是一族了 —— 这一步「什么都不该做」
1 4 5      合并 {4,5}
1 1 4      ★ 注意 a=1 此刻**不是**它那一族的祖宗
2 3 5      → Y
1 6 7      合并 {6,7}
1 5 6      合并成 {1,2,3,4,5,6,7}
2 1 7      → Y
2 8 1      → N（8 号一直是自己一族）

答案：N Y Y Y N，最后一行 2（{1..7} 和 {8}）。

• 第 5 步那个重复合并，是「无条件 cnt--」这个 bug 的唯一现场；
• 第 7 步那个「a 不是祖宗」，是「只挂点不挂族」和「比爸爸不比祖宗」的现场；
• 而第 8、11 步的查询，是把上面两件事读出来的地方 —— ★ bug 要现形，得「先埋下、后读出」两件事都发生，这正是第 12 步生成器调不动的根源。

正解维护的是一片森林，把信息一路攒下来。要是标准答案也维护森林， 两份代码就是同一个思路写了两遍 —— 只能验出打字错误，验不出想法错误 （第 9、15、34、35 章那条）。

所以这一份什么都不攒：合并只是把边记下来，查询时拿现有的边从零建一遍图、 从 a 出发 BFS，看 b 在不在里面。

★ 而且 BFS 里一次 break 都没有 —— 哪怕半路撞见 b，也要把 a 的连通块整个走完。 （第 31 章：「找到第一个就 break」会让暴力假装自己不慢； 第 35 章补的后半句：标准答案要挑「没有 break」的那个思路。）

合并两棵树时，只有一件事可以选：谁挂到谁下面。

if (rk[ra] > rk[rb]) swap(ra, rb);   // 保证 ra 那棵不比 rb 那棵高
fa[ra] = rb;                          // ★ 矮的挂到高的
if (rk[ra] == rk[rb]) rk[rb]++;       // 只有一样高，接起来才真的高了一层

为什么方向是这个？把 A 挂到 B 下面，A 里所有点到根的距离都 +1，B 里一个都不变 —— 那当然要让矮的那边去承担这个 +1。（第 35 章「弹出方向由你要问的问题决定」的同一句话。）

★ 证明（对 r 做归纳）：秩为 r 的树至少有 2^r 个点。

• r = 0：一个孤立点，2⁰ = 1 个，成立。
• 秩什么时候会涨？只有两棵秩都是 r−1 的树合并时，新树的秩才变成 r。 而这两棵按归纳假设各自至少有 2^(r−1) 个点，合起来至少 2^r 个。∎

于是：树高 ≤ 秩 ≤ log₂ n。n = 2×10⁵ 时，这个上界只有 17。

★ 这是这一章唯一一条能当场证完的界。 后面 α(n) 那条只给结论加实测 —— 说清楚哪句证明了、哪句没证，比含糊过去要紧得多。

拿最刁钻的合并顺序（./genBig n 2：两两配对、一层一层往上合）去打它：

每一行都正好是 ⌊log₂ n⌋ —— 界是紧的，而且要专门造数据才顶得到 （第 33 章那条：要证明一个下界是紧的，就得自己造出那个最坏情况）。

./genBig 16000 2 | ./count      # 看 rankOnly 那一行的「最终树高」

int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];        // 第一趟：找到祖宗
    while (fa[x] != r) {                 // ★ 第二趟：路径压缩
        int nx = fa[x]; fa[x] = r; x = nx;
    }
    return r;
}

★ 它的账和第 35 章是同一种账，但难得多：

• 第 35 章：「每个元素一辈子只能出栈一次」—— 一句话就说完了，总量被一个常数管死；
• 这一章：一次 find 可以很贵（走一条长路），可它走过之后那条路就没了 —— 贵的那一次，把后面无数次变便宜了。

★ 这才是「均摊」的本意：不是「每次都便宜」，是「贵的那几次自己把账付了」。

两句话一起上，每次操作的均摊代价是 O(α(n))。α 是反阿克曼函数， n < 2^65536 时 α(n) ≤ 5 —— 所以它「几乎是常数」，但它不是常数。

⚠ 老实话写在这里：α 那条界这一章不证（完整证明要用势函数分层，超出这本书的范围）。 这一章用实测代替：第 8 步那张表会让你亲眼看到三条曲线的增长率。

half.cpp 那句 fa[x] = fa[fa[x]] 每路过一个点就把它挂到爷爷身上，这条路当场短一半； 它只走一趟，均摊复杂度和「压到根」同一个量级。

★ 第 35 章那条「>= 和 > 怎么写都对」的第二次，而这次「都对」的分量不一样： 那一章两种写法答案相同、过程不同；这一章两种写法连复杂度量级都相同，差的只是常数。 「都对」也分好几种，说清楚是哪一种才算说清楚。

• naive 4.00 —— n 翻倍它翻四倍，这是 Θ(n²) 的签名。16 000 个点就要跳 1.7 亿步；
• compress 2.13、half 2.07 —— 略微超线性，那个「略微」就是 log 级别的东西；
• fast 2.00 —— 干干净净的线性。每次操作的代价在这段范围里根本没涨。

★ 请注意 fast 那一列的绝对值：39 984 ≈ 操作条数 × 1.25。 平均每次 find 只往上跳一步多一点点 —— 这就是「几乎是 O(1)」长的样子。

⚠ 但别把 α(n) 读成「常数」：这段实测跨了 16 倍的 n，而 α 在这个范围里根本没变过 （α 要涨 1，n 要翻的是指数塔）。实测看不出它不是常数，这恰恰是它的可怕之处。

播一遍你会看到：

• 画面下方那行结论（Y / N / 合并 / 已同族）两边永远一模一样；
• 右上角那两个「累计跳步」越拉越开；
• 右边那棵树被压缩「拍扁」的那一刻很好认：某个点的爸爸突然直接变成了根。

把数据切到「★ 链式合并」那一档，左边会长成一条越来越长的链，右边始终是一棵扁扁的星形树。 再切到「⚠ 两两配对」那一档 —— 两边几乎一样扁，这就是第 9 步那句 「顺手写法会把差距藏起来」在画面上的样子。

⚠ 动画和 trace.cpp 在 check:viz 里是逐步对的：每一步两边的 find 路径、 这一步跳了几步、累计跳了几步、fa 数组、rk 数组，全部逐字节比 （不只对最终答案 —— 第 21 章以来那条规矩）。

点「运行 ▶」看结果

int find(int x) { while (fa[x] != x) x = fa[x]; fa[x] = x; return x; }
//                                             ~~~~~~~~~ 此刻 x 早就是根了

循环停下来时 x 已经变成了根，于是 fa[x] = x 是把根挂到根自己身上 —— 一句空话。

★ fakeCompress ≡ naive：不只是答案一样，跳步数一个数字都不差 （1 000 / 2 000 / 4 000 / 8 000 / 16 000 五个规模全部逐字节相同，钉在 check:viz 里）。 这是本教材第十二条恒等式（前十一条在第 23~28、34、35 章）。

⚠ 而它和前十一条有一个本质区别：前面那些恒等式两边都是「答案」，这一条两边是「开销」。

点「运行 ▶」看结果

while (fa[x] != r) { fa[x] = r; x = fa[x]; }              // ✗ x 直接跳到 r，循环立刻结束
while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; } // ✓ 先把「原来的爸爸」存下来

它比上一个温和：每次 find 至少还是把起点挂到了根上。 代价是跳步数从 20 万涨到 131 万（n = 16 000），介于 naive 和 compress 之间 —— 温和正是它更难被发现的原因。

点「运行 ▶」看结果

if (rk[ra] < rk[rb]) swap(ra, rb);   // ✗ 反了
if (rk[ra] > rk[rb]) swap(ra, rb);   // ✓

实测（链式数据）：它的跳步数在五个规模上和「根本没写按秩合并」的 compress.cpp 一模一样 （10 003 / 20 882 / 45 005 / 96 775 / 204 304）。

★ 把方向写反，效果等于没写。 那句 swap 白写了，rk 数组也白维护了。 ⚠ 但这条「相等」是实测出来的，不是证出来的 —— 第 2 步那组小数据上它俩就不相等 （13 vs 15）。一个方向能证明，反过来只是实测没碰到反例 （第 35 章「忘弹队头 vs 出界差一」的同款分寸）。

⚠ 还要注意它没有慢到天上去：路径压缩很宽容，它会把按秩合并的错误一路补回来。 这正是「只写路径压缩」能在竞赛里活到今天的原因。

★★ 对拍验的是「两份代码想的是不是同一件事」，验不了「它跑得快不快」。

所有只影响复杂度、不影响答案的写法，对拍原理上全都看不见。

这是随机对拍的第四个盲区，而且它比前三个都要普遍：

1. 第 20 章：对拍只能证伪，不能证明「对」；
2. 第 31 章：验证器证明不了「答案存在时你没漏报」；
3. 第 33 章：随机数据碰不到最坏情况（下界紧不紧，随机对拍答不了）；
4. ★ 第 36 章（本章）：对拍看不见「慢」。第 35 章那个溢出是它的一个特例 （溢出改答案、只是小数据碰不到；而这一章的五份代码连答案都不改）。

想抓这一类 bug，只有一条路：换尺子。 数次数（count.cpp），别只看答案。

点「运行 ▶」看结果

第 2 步那组数据上它给 N Y N N N（正解 N Y Y Y N）。 ⚠ 第 34 章已经讲过它为什么错，这一章只补那一章没做的事：量一量几轮能抓住。

点「运行 ▶」看结果

它给 N Y N Y N —— 只错在第 3 个查询上。 ★ 它错得比上一个隐蔽：a 自己连过去了，a 的子孙也跟着过去了，掉队的是 a 的祖宗那一支。

点「运行 ▶」看结果

它的 Y / N 五个全对，只有最后一行是 1（正解 2）—— 第 2 步第 5 行那次重复合并多减了一次。

gen.cpp 带了八个档位（./gen 种子 档位），种子固定 1..300：

★ 档位 2 是这一章最响的一记耳光。 我的推理是这样的： 三个 bug 都要「深度 ≥ 2」才现形，那就让合并的两头都落在已经被合过的点上， 新树自然长在旧树上 —— 听起来无懈可击。

实测：两个 bug 一起变成 0 / 300。

原因一句话：两头都是老点，合并就几乎总是撞上同一族 —— 300 轮里 295 轮出现重复合并，可合并全成了空转，森林压根没长起来。 我以为自己在造深度，其实是在造「什么都不做」。

★ 第 31 章那条「某一支占得太多，会吃掉别人」的第六次， 而且这次是我亲手把那一支喂到 295 / 300 的。 ⚠ 档位 3（重复点对）是同一个毛病的轻症版：5 / 30 / 249。

★ 档位 5 更刺眼：单看这一行，「点数放大」是个灾难 —— 比爸爸从 11 掉到 3，挂点不挂族从 46 掉到 19，无条件 cnt— 从 179 掉到 117。 任何一个只看单行表的人都会当场把它扔掉。 别急，看下一张表。

• 「点数放大」单独加是 11 → 3（灾难），加在「操作数顶上去」之后是 223 → 267。 道理其实很直白：点多了，就需要更长的操作序列才攒得出一棵深树； 序列不够长时点越多越稀，序列够长时点多才有地方长。

  ★★ 第 32、34、35 章那条「调优不可加：一处改动值不值得留，取决于其它旋钮此刻在哪」 的第四次，而这次的形状最刺眼：一处单独看是负分的改动，最后被留下了。

• 档位 7 是在最终环境里重新量「重复点对」（第 34 章那条）：267 → 251，仍然有害，撤回。 ⚠ 但请注意它在档位 3 那里是 11 → 5（几乎全灭），到最终环境只剩 −16 —— 同一处改动的危害，也是随环境变的。

★ 最后定档的标准照旧：让最弱的那一支尽量强（不是平均分最高）—— 最弱的一直是「比爸爸不比祖宗」，档位 6 把它顶到了 267。

【1】★★ 对拍看不见「慢」。 本章八种写法答案完全相同，对拍 0 / 300。 所有只影响复杂度、不影响答案的写法，对拍原理上全都抓不到。 这是随机对拍的第四个盲区（前三个：只能证伪 / 验证器证不了没漏报 / 碰不到最坏情况）。 ★ 换尺子：数次数，别只看答案；而且次数可复现，秒数不可复现。

【2】★ 按秩合并那条界能证，α(n) 那条不证。 秩为 r 的树至少 2^r 个点 ⇒ 树高 ≤ log₂ n（n = 2×10⁵ 时只有 17）—— 三行归纳就完了， 而且实测能顶到 ⌊log₂ n⌋（要专门造数据）。 α(n) 这一章只给结论 + 三条实测曲线。说清楚哪句证了、哪句没证，比含糊过去要紧。

【3】★ 均摊的第二课：不是「每次都便宜」，是「贵的那几次自己把账付了」。 一次 find 可以走很长一条路，但它走过之后那条路就没了。 第 35 章那句「每个元素一辈子只能出去一次」是这件事的入门版。

【4】★ 复杂度是增长率，不是某一个数据点。 n = 8 的时候正解排倒数第三（16 步 vs naive 的 18 步）； 要看清差别，必须让 n 翻倍着走：翻倍比 4.00 / 2.84 / 2.13 / 2.00 才是那三条曲线的本体。

【5】★ 这一章的生成器把「调优不可加」推到了新的高度。

• 「合并两头都从老点里挑」本以为在造深度，实际造出了 295 / 300 的空转合并， 两个真 bug 一起变成 0 / 300；
• 「点数放大」单独加是灾难（11 → 3），配上「操作序列拉长」却是最好的一档（223 → 267）—— 一处单独看是负分的改动，最后被留下了。

★ 所以：每一处改动都要在最终环境里重新量一遍，而且别指望旋钮能一条条叠加。