LeetCode 题解工作台
连通网络的操作次数
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1 。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b 。 网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。 给你这个计算机…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们可以用并查集维护计算机之间的联通关系。遍历所有的连接，对于每个连接 $(a, b)$，如果 和 已经联通，那么这个连接是多余的，我们将多余的连接数加一；否则，我们将 和 连通，然后将联通分量数减一。 最后，如果联通分量数减一大于多余的连接数，说明我们无法使所有计算机联通，返回 -1；否则，返回联通分量数减一。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
用以太网线缆将 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 解释：线缆数量不足。
示例 4：
输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]] 输出：0
提示：
1 <= n <= 10^51 <= connections.length <= min(n*(n-1)/2, 10^5)connections[i].length == 20 <= connections[i][0], connections[i][1] < nconnections[i][0] != connections[i][1]- 没有重复的连接。
- 两台计算机不会通过多条线缆连接。
解题思路
方法一：并查集
我们可以用并查集维护计算机之间的联通关系。遍历所有的连接，对于每个连接 ，如果 和 已经联通，那么这个连接是多余的，我们将多余的连接数加一；否则，我们将 和 连通，然后将联通分量数减一。
最后，如果联通分量数减一大于多余的连接数，说明我们无法使所有计算机联通，返回 -1；否则，返回联通分量数减一。
时间复杂度 ，空间复杂度 。其中 和 分别是计算机的数量和连接的数量。
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
cnt = 0
p = list(range(n))
for a, b in connections:
pa, pb = find(a), find(b)
if pa == pb:
cnt += 1
else:
p[pa] = pb
n -= 1
return -1 if n - 1 > cnt else n - 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate recognizes the importance of connectivity before counting extra cables.
- question_mark
Observe whether they correctly identify the minimum number of cables needed based on graph traversal techniques.
- question_mark
Look for handling of edge cases such as insufficient connections or unreachable components.
常见陷阱
外企场景- error
Misunderstanding the minimum cable count required when multiple disconnected components exist.
- error
Failing to detect when it's impossible to connect all computers, like when the number of cables is less than `n - 1`.
- error
Confusing the number of operations required with the number of components, leading to an incorrect solution.
进阶变体
外企场景- arrow_right_alt
Change the graph structure to a directed graph and adjust the problem accordingly.
- arrow_right_alt
Consider the case where the computers are initially connected in a cycle and add extra disconnections to the problem.
- arrow_right_alt
Increase the graph's size to test for scalability and performance in larger networks.