雲端 Mac 上的 Swift 並查集測試：連通性與元件計數

離線聯絡人分組、裝置關聯與圖片分群，經常需要判斷「兩個物件是否屬於同一組」。如果連線只會新增、不會刪除，並查集比反覆走訪所有關係更合適；如果還需要說明連線路徑，或經常撤銷連線，就應保留原始圖形，改用圖形走訪或專門的動態資料結構。將這段純 Swift 邏輯納入雲端 Mac 的建置前檢查，就能先找出分組錯誤，再進入耗時的應用程式建置流程。

先定義輸入與可觀察的結果

本文使用無向連線，節點編號固定為 0..<n。業務邏輯層必須先將穩定的識別碼對應到整數，不能使用陣列中目前的顯示位置，否則清單重新排序就會改變物件身分。對應表與連線資料應來自同一份快照。

驗收只觀察三件事：兩個節點是否連通、剩餘的連通元件數，以及某個節點所屬元件的大小。重複連線與自環都不能減少元件數；只有原本不連通的兩組成功合併時，計數才減一。

根節點只是實作細節，不是業務上的分組編號。同一組連線若以不同順序輸入，代表元可能改變，但連通關係必須保持一致。

無效索引應在匯入層拒絕，並記錄行號或資料識別碼。以下實作用前置條件表達內部約束，不會將靜默忽略錯誤輸入視為容錯機制。

撰寫可獨立執行的實作

將以下內容儲存為 union_find_check.swift。依大小合併會將小樹接到大樹下，路徑壓縮則讓查詢經過的節點直接指向根。大小資訊只在根節點上有效，不能直接讀取任意位置的 sizes。

struct UnionFind {
    private var parent: [Int]
    private var sizes: [Int]
    private(set) var components: Int

    init(_ count: Int) {
        precondition(count >= 0)
        parent = Array(0..<count)
        sizes = Array(repeating: 1, count: count)
        components = count
    }

    mutating func root(_ node: Int) -> Int {
        precondition(parent.indices.contains(node))
        var r = node
        while parent[r] != r {
            r = parent[r]
        }
        var current = node
        while parent[current] != current {
            let next = parent[current]
            parent[current] = r
            current = next
        }
        return r
    }

    @discardableResult
    mutating func union(_ a: Int, _ b: Int) -> Bool {
        var ra = root(a)
        var rb = root(b)
        guard ra != rb else { return false }
        if sizes[ra] < sizes[rb] {
            swap(&ra, &rb)
        }
        parent[rb] = ra
        sizes[ra] += sizes[rb]
        components -= 1
        return true
    }

    mutating func connected(_ a: Int, _ b: Int) -> Bool {
        let ra = root(a)
        let rb = root(b)
        return ra == rb
    }

    mutating func size(of node: Int) -> Int {
        let r = root(node)
        return sizes[r]
    }
}

查詢會改寫路徑，因此方法標記為 mutating。不要將同一個實例直接交給多個並行任務修改；可以將一次分組計算放在單一任務內，完成後輸出不可變的結果。若以 actor 包裝，也應讓一批連線在不跨越暫停點的操作中處理完畢。

用圖形走訪交叉核對每次合併

只寫下幾個預期的根節點編號，很容易讓測試與實作出現同一種錯誤。更可靠的參照是鄰接串列走訪：它不使用父節點指標，也不依賴合併策略。將以下程式碼接在同一個檔案的末尾，逐次加入連線，並核對所有節點配對。

func reachable(_ start: Int, in graph: [[Int]]) -> Set<Int> {
    var seen: Set<Int> = [start]
    var stack = [start]
    while let node = stack.popLast() {
        for next in graph[node] {
            if seen.insert(next).inserted {
                stack.append(next)
            }
        }
    }
    return seen
}

func verify(_ edges: [(Int, Int)], count: Int) {
    var uf = UnionFind(count)
    var graph = Array(repeating: [Int](), count: count)

    for (a, b) in edges {
        let expectedMerge = !reachable(a, in: graph).contains(b)
        precondition(uf.union(a, b) == expectedMerge)
        graph[a].append(b)
        graph[b].append(a)

        var unseen = Set(0..<count)
        var expectedComponents = 0
        for node in 0..<count {
            let group = reachable(node, in: graph)
            if unseen.contains(node) {
                expectedComponents += 1
                unseen.subtract(group)
            }
            precondition(uf.size(of: node) == group.count)
            for other in 0..<count {
                precondition(
                    uf.connected(node, other) == group.contains(other)
                )
            }
        }
        precondition(uf.components == expectedComponents)
    }
}

let edges = [(0, 1), (2, 3), (1, 2), (0, 3), (4, 4)]
verify(edges, count: 6)
verify(Array(edges.reversed()), count: 6)
precondition(UnionFind(0).components == 0)

這裡同時涵蓋了跨組合併、重複連線、孤立節點與自環。反向執行並不是要求中間狀態相同，而是要求每一步都符合當下的圖形。最終分組也不應受到輸入順序影響。

小規模資料適合在每一步進行完整核對；大規模資料則先在小圖形上窮舉邊的子集，再以固定種子進行抽樣。發生失敗時，應儲存完整的邊序列，不能只保留隨機種子，因為產生器或產生規則也可能改變。

納入建置前檢查，並區分正確性與效能

先確認節點已安裝所需的工具鏈，再於指令碼所在目錄執行：

set -eu
xcrun swift --version
xcrun swift union_find_check.swift

指令碼正常結束即代表通過，前置條件失敗則會回傳非零狀態。將指令碼與測試資料提交至儲存庫，讓流水線直接使用結束狀態，不必解析本地化輸出。不要使用會移除前置條件檢查的 -Ounchecked 來編譯這個驗收程式。

如何單獨驗收路徑壓縮

連通性正確，不代表路徑壓縮已經生效。可以在測試專用建置中加入唯讀的深度檢查：先建立多層樹，查詢其中一個深層節點，再確認它已直接指向根。不要為了測試，就在業務介面開放可寫入的父節點陣列。

效能檢查應另外使用較大的輸入，分別記錄首次查詢與重複查詢。不要將完整圖形走訪的參照運算納入計時，也不要拿某次雲端執行的毫秒數作為所有機器的硬性門檻；比較父節點指標的存取次數，是更穩定的檢查方式。

將失敗原因定位到明確的邊界

元件數異常，通常是因為重複合併時仍將計數減一；元件大小偏大，應先檢查自環與重複邊；合併後部分節點仍不連通，則要檢查是否誤改了輸入節點的父節點指標，而不是根節點的父節點指標。針對每種故障保留一個最小邊序列，比留下大量業務資料更容易進行迴歸測試。

輸入層應另外測試負數、等於節點總數的編號，以及未登錄的識別碼，確認它們在進入資料結構前就被拒絕。空集合不允許查詢節點，但應正常回報零個元件。

最後要明確界定刪除操作的能力邊界：路徑壓縮會丟失原始連線的形狀，不能只修改一個父節點指標就實現「解除關係」。連線數量不大時，從剩餘的邊重建最簡單；需要回滾時，應採用具備變更日誌的獨立設計，並重新評估路徑壓縮策略。驗收通過的標準是：有效輸入能得到正確分組，無效輸入會明確失敗，超出能力範圍的操作不會被偽裝成成功。

常見問題