1319. Number of Operations to Make Network Connected¶
题目信息¶
- 题号:
1319
- 难度:
Medium
- 主题:
图、并查集、连通分量
- 原题:
- 重点:
可拔下一条已有网线并连接任意两台未直连计算机;至少需要
n-1条网线,答案为连通分量数减一
题目重述¶
有 n 台计算机,connections[i] = [a,b] 表示两台计算机之间有一条网线。一次操作可以移除任意一条现有网线,再用它连接任意两台计算机。
请返回使整个网络连通所需的最少操作数。若现有网线总数不足以连接所有计算机,返回 -1。
1 <= n <= 10^5,连接数不超过 10^5,每条连接的两个端点不同且无重复边。
自建示例¶
冗余环路网线可以连接两个分量:
输入:n = 5, connections = [[0,1],[1,2],[2,0],[3,4]]
输出:1
解释:前三台形成环,可移除其中一条冗余网线并连接两个连通分量。
网线数量不足时无解:
输入:n = 4, connections = [[0,1],[2,3]]
输出:-1
解释:连接四台计算机至少需要三条网线,但当前只有两条。