连通网络的操作次数

连通 n 台电脑至少要 n−1 根线。所以先判线数：不够 n−1 直接 -1；够了，答案就是连通块个数 c 减 1。下面用并查集把这两步演给你看。

初始 · 4 台电脑各自为政：用例 n=4, connections=[[0,1],[0,2],[1,2]]。第一步先数线：有 3 根，n−1=3，3 ≥ 3 线够，不会是 -1。开局每台电脑自成一团，parent[i]=i，c=4。

第 1 根线 [0,1] · 先 find 两根：处理第一根线 [0,1]：先各自 find 找根（两个亮起来的点）。find(0)=0、find(1)=1，两个根不同，说明它俩还没在一团，可以合并。

第 1 根线 [0,1] · union 挂根，c 减 1：把 0 的根挂到 1 的根下：parent[0]=1（看出现了一条 0→1 的箭头）。现在 0、1 同色成一团，连通块数 c 从 4 减到 3。union 挂的是根，不是节点本身。

第 2 根线 [0,2] · 先 find 两根：处理第二根线 [0,2]：find(0) 顺着 0→1 找到根 1，find(2)=2。根不同，可以并。注意 0 已经挂在 1 下面了，find 是一路顺藤摸到最顶上的根。

第 2 根线 [0,2] · union 挂根，c 减 1：把 0 的根(1) 挂到 2 的根下：parent[1]=2。现在 0→1→2 连成一串，根都是 2，{0,1,2} 同色成一团，c 减到 2。0 没被直接动过，却因为传递也并了进来。

第 3 根线 [1,2] · find 两根：处理第三根线 [1,2]：find(1) 走 1→2 根是 2，find(2)=2，两个根相同！说明 1 和 2 早就在一团了。这根线属于多余的——c 不变、不会再减。

所有线处理完 · 数团：三根线走完：0、1、2 归到根 2 是一团；3（亮起来那个）没人连，独自一团。最终连通块数 c=2。那根多余的 [1,2] 正好可以拔下来给 3 用。

答案 = c − 1 = 1：2 个团连成 1 片只要 1 根线。把多余的 [1,2] 拔下接到 3 和 {0,1,2} 之间，全连通 → 答案 c − 1 = 1。

把题目想成地理：每台电脑是一座岛，每根网线是一座桥，已经连在一起的若干岛就是一块「大陆」。问题就变成：还要架几座桥，才能把所有大陆并成一整块？答案就是「大陆数 − 1」。

再走一个大例 · n=7 起手：换个更热闹的：n=7，6 根线 connections=[[0,1],[2,3],[4,5],[1,2],[3,4],[5,6]]。线数 6 = n−1，刚好不多不少。开局 7 台各自一团，c=7。盯住 parent 箭头和右边 c 一帧一帧地变。

线 [0,1] · find 不同根 → 可并：第 1 根线 [0,1]：find(0)=0、find(1)=1，根不同，可以并。两个亮起的点就是这一步在比较的两个根。

线 [0,1] · union → c=6：parent[0]=1，0→1 出现箭头，{0,1} 同色成团。每成功并一次，c 就减 1：7 → 6。

线 [2,3] · find 不同根 → 可并：第 2 根线 [2,3]：find(2)=2、find(3)=3，根不同，可以并。{0,1} 那团原样不动，这一步只看 2 和 3。

线 [2,3] · union → c=5：parent[2]=3，{2,3} 成团。c 又减 1：6 → 5。现在场上有 {0,1}、{2,3} 两团，外加 4、5、6 三个孤岛。

线 [4,5] · find 不同根 → 可并：第 3 根线 [4,5]：下排的 4、5 亮起，find(4)=4、find(5)=5，根不同，可以并。

线 [4,5] · union → c=4：parent[4]=5，{4,5} 成团。c 减到 4。现在三团 {0,1}、{2,3}、{4,5} 加孤岛 6。前 3 根线各并掉一个孤岛，下面 3 根线开始把团跟团接起来。

线 [1,2] · find 不同根 → 团接团：第 4 根线 [1,2]：find(1)=1（{0,1} 的根）、find(2)=3（{2,3} 的根），根不同。这次连的不是两个孤点，而是两整团。

线 [1,2] · union → c=3：parent[1]=3：把 {0,1} 的根 1 挂到 {2,3} 的根 3 下，两团合一变成 {0,1,2,3}（0→1→3 串起来同色）。一根线减一团，c 从 4 减到 3。

线 [3,4] · find 不同根 → 团接团：第 5 根线 [3,4]：find(3)=3（大团的根）、find(4)=5（{4,5} 的根），根不同，可以并。又是两团相接。

线 [3,4] · union → c=2：parent[3]=5：大团的根 3 挂到 5 下，{0,1,2,3} 和 {4,5} 并成 {0,1,2,3,4,5}。c 减到 2，只剩这一大团和孤岛 6 了。

线 [5,6] · find 不同根 → 收尾：第 6 根线 [5,6]：find(5)=5（大团的根）、find(6)=6（孤岛），根不同。最后把 6 也拉进来。

线 [5,6] · union → c=1 全连通：parent[5]=6，7 台电脑全归到同一个根 6，同色一整团。c 从 2 减到 1。只剩一团 = 已全连通，答案 c−1=0，一步都不用挪。这就是「恰好 n−1 根线刚好连满」。

最直觉的想法：试着拔下某根线、再插到某两台电脑之间，看哪种挪法能全连通。可挪法的组合极多，根本试不完，也说不清「最少几步」。我们需要直接算出答案的办法。

其实根本不用模拟拔插。只要线够（≥ n−1），多出来的线一定足够调度。所以答案只取决于现在有几个互不相连的团：c 个团连成一片，缺 c−1 根，答案就是 c−1。问题从「怎么挪」变成「数团」。

n 个点、c 个团，团内部把点连成树共用掉 n−c 根线。手里总线数 ≥ n−1 = (n−c)+(c−1)，减去团内用掉的 n−c 根，剩下的 ≥ c−1 根，正好够把 c 个团串起来。所以线够就一定能办成。

记住骨架：parent 数组、find 顺藤找根、union 把根挂根、count 计团数。凡是「数有几个团 / 判是否全连通」都套它：省份数量、岛屿数量、冗余连接全是它。

易错实演 · 线不够的情形：假设 n=6 却只有 4 根线。连通 6 台至少要 5 根，4 < 5——无论怎么挪，4 和 5（亮起的孤岛）永远有一个连不进来，所以开头那一句直接返回 -1，根本不用数团。

边界三连：特别留意单台电脑 n=1：它自己就是连通的，需要 0 步。还有线数恰好 n−1 且全连通时，c=1，答案 0。

面试常追问「为什么是并查集」「答案为何只看团数」，把「数连通块 + 缺 c−1 根线」这个本质讲透就稳了。