【資料結構與演演算法】之連通網路的操作次數的演演算法

一、題目要求

• 用乙太網線纜將 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
    }
 }