Medium

题目描述

用以太网线缆将 n 台计算机连接成一个网络，计算机编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。

提示：

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n * (n - 1) / 2, 10^5)
  • connections[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 没有重复的连接。
  • 两台计算机不会通过多条线缆连接。

解题思路

这是一个图论连通性问题，关键在于理解两个要点：

核心思路：

  1. 要使 n 台计算机全连通，至少需要 n-1 条线缆
  2. 如果当前有 k 个连通分量，需要 k-1 次操作来连接它们

解题步骤：

  • 首先检查线缆数量是否足够：如果 connections.length < n-1，返回 -1
  • 使用并查集或 DFS/BFS 找出当前网络中连通分量的个数
  • 连通分量个数减 1 就是所需的最少操作次数

为什么这样可行？ 当我们有足够的线缆时，多余的线缆可以被重新利用。每个连通分量内部已经连通，我们只需要在不同连通分量之间建立连接。如果有 k 个连通分量，需要 k-1 条线缆将它们连成一个整体。

三种常见解法：

  1. 并查集（推荐）：效率高，代码简洁
  2. DFS：直观易懂，适合理解图的连通性
  3. BFS：与DFS类似，层序遍历找连通分量

代码实现

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        int components = n;
        for (auto& conn : connections) {
            int rootA = find(conn[0]), rootB = find(conn[1]);
            if (rootA != rootB) {
                parent[rootA] = rootB;
                components--;
            }
        }
        
        return components - 1;
    }
};

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        components = n
        for a, b in connections:
            rootA, rootB = find(a), find(b)
            if rootA != rootB:
                parent[rootA] = rootB
                components -= 1
        
        return components - 1

public class Solution {
    public int MakeConnected(int n, int[][] connections) {
        if (connections.Length < n - 1) return -1;
        
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int Find(int x) {
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }
        
        int components = n;
        foreach (var conn in connections) {
            int rootA = Find(conn[0]), rootB = Find(conn[1]);
            if (rootA != rootB) {
                parent[rootA] = rootB;
                components--;
            }
        }
        
        return components - 1;
    }
}

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) return -1;
    
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    let components = n;
    for (const [a, b] of connections) {
        const rootA = find(a), rootB = find(b);
        if (rootA !== rootB) {
            parent[rootA] = rootB;
            components--;
        }
    }
    
    return components - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
并查集O(m·α(n))O(n)
DFS/BFSO(m + n)O(m + n)

其中 m 是连接数，α(n) 是阿克曼函数的反函数，几乎为常数。并查集解法最优。