省份数量

记住这套「各找老大 → 老大不同就合并、省份减一 → 老大相同就跳过」，下面每条相连关系都在套它。

准备 · 各自为省：开局：6 个城市各自为省，每个城市的老大都是自己（没有箭头）。省份数从 6 起步，接下来按相连关系一对对合并。

看 (0, 1)：相连关系 (0, 1)：城市 0 和 1 直接相连，先各自往上找老大（根）。

找根 · 0→0, 1→1：顺着父指针往上爬：0 的根是 0，1 的根是 1。两者根不同。比的是根、不是直接父亲。

合并 · 根 0→1：0 的老大是 0、1 的老大是 1，不同根 → 合并！把根 0 挂到根 1 下面，两省并成一省，省份数减一变成 5。

看 (1, 2)：相连关系 (1, 2)：城市 1 和 2 直接相连，先各自往上找老大（根）。

找根 · 1→1, 2→2：顺着父指针往上爬：1 的根是 1，2 的根是 2。两者根不同。比的是根、不是直接父亲。

合并 · 根 1→2：1 的老大是 1、2 的老大是 2，不同根 → 合并！把根 1 挂到根 2 下面，两省并成一省，省份数减一变成 4。

看 (0, 2)：相连关系 (0, 2)：城市 0 和 2 直接相连，先各自往上找老大（根）。

找根 · 0→2, 2→2：顺着父指针往上爬：0 的根是 2，2 的根是 2。两者同根。比的是根、不是直接父亲。

跳过 · 已同省 2：0 和 2 的老大都是 2，已经同省了，无需合并，直接跳过。省份数不变，还是 4。

看 (3, 4)：相连关系 (3, 4)：城市 3 和 4 直接相连，先各自往上找老大（根）。

找根 · 3→3, 4→4：顺着父指针往上爬：3 的根是 3，4 的根是 4。两者根不同。比的是根、不是直接父亲。

合并 · 根 3→4：3 的老大是 3、4 的老大是 4，不同根 → 合并！把根 3 挂到根 4 下面，两省并成一省，省份数减一变成 3。

看 (4, 5)：相连关系 (4, 5)：城市 4 和 5 直接相连，先各自往上找老大（根）。

找根 · 4→4, 5→5：顺着父指针往上爬：4 的根是 4，5 的根是 5。两者根不同。比的是根、不是直接父亲。

合并 · 根 4→5：4 的老大是 4、5 的老大是 5，不同根 → 合并！把根 4 挂到根 5 下面，两省并成一省，省份数减一变成 2。

看 (3, 5)：相连关系 (3, 5)：城市 3 和 5 直接相连，先各自往上找老大（根）。

找根 · 3→5, 5→5：顺着父指针往上爬：3 的根是 5，5 的根是 5。两者同根。比的是根、不是直接父亲。

跳过 · 已同省 5：3 和 5 的老大都是 5，已经同省了，无需合并，直接跳过。省份数不变，还是 2。

完成 · 数根：所有相连关系处理完，城市归并成 2 棵树（2 个不同的根）——也就是 2 个省。同色的城市同属一省。这就是并查集数连通块的全部威力。

边界先想清：互不相连取 n、全相连取 1、单城取 1——靠「初始 count=n + 每次成功合并减一」自然得出。

三个高频追问：路径压缩+按秩合并两大优化、DFS 等价解法、以及并查集的最佳适用场景。