Python

Python 實作 Disjoint Set 與 Union Find

使用情境 在 Leetcode 寫到一題: 1319. Number of Operations to Make Network Connected 現在有 n 台電腦以及一些 cables 將電腦點對點連接,問需要移動至少幾條 cable 才能讓在所有電腦連成單一網路。 以 graph 的角度來看,電腦就是 nodes,cables 就是 edges。 要將整張 graph 連接起來,至少需要 n-1 個 edges。若一個 graph 裡面有超過 n-1 個 edges,剩下的就是多出來的 edges,可以供我們拿來移動的 edges。 所以第一件事就是要檢查 edges 數量 >= n-1。 當檢查完畢之後,我們有至少 n-1 條 edges,一定可以用這些 edges 將所有 nodes 連接起來。 因為題目只問需要移動幾條 edges,我們可以假設我們