一、題目要求
- 用以太網線纜將 n 臺計算機連接成一個網路，計算機的編號從 0 到 n-1，線纜用 connections 表示，其中 connections[i] = [a, b] 連接了計算機 a 和 b，
- 網路中的任何一臺計算機都可以通過網路直接或者間接訪問同一個網路中其他任意一臺計算機，
- 給你這個計算機網路的初始布線 connections，你可以拔開任意兩臺直連計算機之間的線纜，并用它連接一對未直連的計算機，請你計算并回傳使所有計算機都連通所需的最少操作次數，如果不可能，則回傳 -1 ，
- 示例一：
輸入：n = 4, connections = [[0,1],[0,2],[1,2]]
輸出：1
解釋：拔下計算機 1 和 2 之間的線纜，并將它插到計算機 1 和 3 上，
- 示例二：
輸入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
輸出：2
- 示例三：
輸入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
輸出：-1
解釋：線纜數量不足，
- 示例四：
輸入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
輸出：0
- 提示：
- 1 <= n <= 10^5
- 1 <= connections.length <= min(n*(n-1)/2, 10^5)
- connections[i].length == 2
- 0 <= connections[i][0], connections[i][1] < n
- connections[i][0] != connections[i][1]
- 沒有重復的連接，
- 兩臺計算機不會通過多條線纜連接，
二、演算法思路
三、示例演算法
- Swift 示例
class Solution {
class DSU {
private var parent: [Int]
private var compomentsCount: Int
init(_ size: Int) {
parent = Array<Int>(0...size)
compomentsCount = size
}
func find(_ node: Int) -> Int {
var current = node
while parent[current] != current {
current = parent[current]
}
var temp = node
while parent[temp] != current {
(temp,parent[temp]) = (parent[temp],current)
}
return current
}
func join(_ first: Int, _ second: Int) {
let firstRoot = find(find(first))
let secondRoot = find(second)
guard firstRoot != secondRoot else {
return
}
compomentsCount -= 1
parent[firstRoot] = secondRoot
}
func getCompomentsCount() -> Int {
return compomentsCount
}
}
func makeConnected(_ n: Int, _ connections: [[Int]]) -> Int {
guard connections.count >= n - 1 else {
return -1
}
let dsu = DSU(n)
connections.forEach {
dsu.join($0[0], $0[1])
}
return dsu.getCompomentsCount() - 1
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/192622.html
標籤：java