连通网络的操作次数 图解题解

这道题到底在问什么

输入

n=4, connections=[[0,1],[0,2],[1,2]]

输出

1

另一例

n=6, 线不够时 → -1

最优解：一步一步想明白

1. 3连通 n 台电脑至少要 n−1 根线。所以先判线数：不够 n−1 直接 -1；够了，答案就是连通块个数 c 减 1。下面用并查集把这两步演给你看。
2. 4先判线数：3 根 ≥ n−1=3 ✓，parent=[0,1,2,3]，c=4用例 n=4, connections=[[0,1],[0,2],[1,2]]。第一步先数线：有 3 根，n−1=3，3 ≥ 3 线够，不会是 -1。开局每台电脑自成一团，parent[i]=i，c=4。
3. 5find(0)=0, find(1)=1 不同 → 可并处理第一根线 [0,1]：先各自 find 找根（两个亮起来的点）。find(0)=0、find(1)=1，两个根不同，说明它俩还没在一团，可以合并。
4. 6parent[0]=1，{0,1} 一团，c=3把 0 的根挂到 1 的根下：parent[0]=1（看出现了一条 0→1 的箭头）。现在 0、1 同色成一团，连通块数 c 从 4 减到 3。union 挂的是根，不是节点本身。
5. 7find(0)=1, find(2)=2 不同 → 可并处理第二根线 [0,2]：find(0) 顺着 0→1 找到根 1，find(2)=2。根不同，可以并。注意 0 已经挂在 1 下面了，find 是一路顺藤摸到最顶上的根。
6. 8parent[1]=2，{0,1,2} 一团，c=2把 0 的根(1) 挂到 2 的根下：parent[1]=2。现在 0→1→2 连成一串，根都是 2，{0,1,2} 同色成一团，c 减到 2。0 没被直接动过，却因为传递也并了进来。
7. 9find(1)=2, find(2)=2 相同 → 已同团处理第三根线 [1,2]：find(1) 走 1→2 根是 2，find(2)=2，两个根相同！说明 1 和 2 早就在一团了。这根线属于多余的——c 不变、不会再减。
8. 10{0,1,2} 一团 + {3} 一团 → c=2三根线走完：0、1、2 归到根 2 是一团；3（亮起来那个）没人连，独自一团。最终连通块数 c=2。那根多余的 [1,2] 正好可以拔下来给 3 用。
9. 11把 2 个团串起来需 1 根线2 个团连成 1 片只要 1 根线。把多余的 [1,2] 拔下接到 3 和 {0,1,2} 之间，全连通 → 答案 c − 1 = 1。
10. 12把题目想成地理：每台电脑是一座岛，每根网线是一座桥，已经连在一起的若干岛就是一块「大陆」。问题就变成：还要架几座桥，才能把所有大陆并成一整块？答案就是「大陆数 − 1」。
11. 13线数 6 ≥ n−1=6 ✓，parent 各自为政，c=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 一帧一帧地变。
12. 14find(0)=0, find(1)=1 不同第 1 根线 [0,1]：find(0)=0、find(1)=1，根不同，可以并。两个亮起的点就是这一步在比较的两个根。
13. 15parent[0]=1，{0,1} 一团parent[0]=1，0→1 出现箭头，{0,1} 同色成团。每成功并一次，c 就减 1：7 → 6。
14. 16find(2)=2, find(3)=3 不同第 2 根线 [2,3]：find(2)=2、find(3)=3，根不同，可以并。{0,1} 那团原样不动，这一步只看 2 和 3。
15. 17parent[2]=3，{2,3} 一团parent[2]=3，{2,3} 成团。c 又减 1：6 → 5。现在场上有 {0,1}、{2,3} 两团，外加 4、5、6 三个孤岛。
16. 18find(4)=4, find(5)=5 不同第 3 根线 [4,5]：下排的 4、5 亮起，find(4)=4、find(5)=5，根不同，可以并。
17. 19parent[4]=5，{4,5} 一团parent[4]=5，{4,5} 成团。c 减到 4。现在三团 {0,1}、{2,3}、{4,5} 加孤岛 6。前 3 根线各并掉一个孤岛，下面 3 根线开始把团跟团接起来。
18. 20find(1)=1, find(2)=3 不同第 4 根线 [1,2]：find(1)=1（{0,1} 的根）、find(2)=3（{2,3} 的根），根不同。这次连的不是两个孤点，而是两整团。
19. 21parent[1]=3，{0,1,2,3} 一大团parent[1]=3：把 {0,1} 的根 1 挂到 {2,3} 的根 3 下，两团合一变成 {0,1,2,3}（0→1→3 串起来同色）。一根线减一团，c 从 4 减到 3。
20. 22find(3)=3, find(4)=5 不同第 5 根线 [3,4]：find(3)=3（大团的根）、find(4)=5（{4,5} 的根），根不同，可以并。又是两团相接。
21. 23parent[3]=5，{0,1,2,3,4,5} 一团parent[3]=5：大团的根 3 挂到 5 下，{0,1,2,3} 和 {4,5} 并成 {0,1,2,3,4,5}。c 减到 2，只剩这一大团和孤岛 6 了。
22. 24find(5)=5, find(6)=6 不同第 6 根线 [5,6]：find(5)=5（大团的根）、find(6)=6（孤岛），根不同。最后把 6 也拉进来。
23. 25parent[5]=6，7 台归一团parent[5]=6，7 台电脑全归到同一个根 6，同色一整团。c 从 2 减到 1。只剩一团 = 已全连通，答案 c−1=0，一步都不用挪。这就是「恰好 n−1 根线刚好连满」。
24. 26最直觉的想法：试着拔下某根线、再插到某两台电脑之间，看哪种挪法能全连通。可挪法的组合极多，根本试不完，也说不清「最少几步」。我们需要直接算出答案的办法。
25. 27其实根本不用模拟拔插。只要线够（≥ n−1），多出来的线一定足够调度。所以答案只取决于现在有几个互不相连的团：c 个团连成一片，缺 c−1 根，答案就是 c−1。问题从「怎么挪」变成「数团」。
26. 28n 个点、c 个团，团内部把点连成树共用掉 n−c 根线。手里总线数 ≥ n−1 = (n−c)+(c−1)，减去团内用掉的 n−c 根，剩下的 ≥ c−1 根，正好够把 c 个团串起来。所以线够就一定能办成。
27. 31记住骨架：parent 数组、find 顺藤找根、union 把根挂根、count 计团数。凡是「数有几个团 / 判是否全连通」都套它：省份数量、岛屿数量、冗余连接全是它。
28. 33n=6, 只有 4 根线 < 5 → -1假设 n=6 却只有 4 根线。连通 6 台至少要 5 根，4 < 5——无论怎么挪，4 和 5（亮起的孤岛）永远有一个连不进来，所以开头那一句直接返回 -1，根本不用数团。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def makeConnected(self, n, connections):
        if len(connections) < n - 1:        # 线不够直接 -1
            return -1
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # 路径压缩
                x = parent[x]
            return x
        count = n                            # 初始 n 个团
        for a, b in connections:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                count -= 1                    # 成功合并，团数 -1
        return count - 1                     # c 个团需 c-1 根线

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        if ((int)connections.size() < n - 1) return -1;
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
        int count = n;
        for (const auto& e : connections) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) { parent[ra] = rb; --count; }
        }
        return count - 1;
    }
};

class Solution {
    int[] parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int count = n;
        for (int[] e : connections) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) { parent[ra] = rb; count--; }
        }
        return count - 1;
    }
}

复杂度

面试官可能追问