問題描述

給出N個點，點與點之間要麼連通要麼不連通，實現連通函數（union）以及判斷兩點是否直接或間接連通（connected）的函數。

初步理解

使用set的概念理解。幾個連通的點組成一個集合，當兩個集合被新加入的線所連通，就把兩個集合合併爲一個大集合。如下圖所示，{1 4 5} 與 {2 3 6 7} 通過2與5的連通，合併爲{1 2 3 4 5 6 7}。

如果使用python，便可以通過遍歷sets的形式判斷兩個待連接的點所在的集合set1和set2，然後實行合併。這個方法在查找函數（connected）的時候，同時需要遍歷sets來尋找兩個點是否同屬於任何一個集合。
此外，課程中提供幾種不同的方法，使用語言爲C++。

Quick Find

具體數據結構：使用一個數據記錄所在集合的代表點，比如下圖，｛3 4 8 9}屬於同一個集合，代表點設爲8， 那麼id[3] = id[4] = id[8] = id[9] = 8。代表點的選擇定爲union函數的第二個參數。

這種方法之所以叫quick-find，是因爲在find的過程中，時間複雜度僅爲O(1)，只需要判斷數組中兩個位置的值是否一致。然而，它的缺點也是非常明顯的，當我們需要對N個點的集合做N次合併時，每次合併需要遍歷一次數組，N次合併便需要訪問N2次。另外，考慮數組值的變化次數，最壞情況下，在一次合併中可以改變N-1次（除去代表點不變）。因此，我們有了第二種解法。

Quick Union

Quick Union的方法使用樹的結構，當合併兩個點時，把左邊點的root改成右邊點的root。判斷兩個點是否連通的時候，就分別查找兩個點的root，如果root相同則連通。

然而，這種方法使得find的功能時間複雜度爲O(n)。

Weighted Quick Union

由於Quick Union構建樹的方法是聯合集合時每次將左邊樹改爲右邊樹的root的子樹，不考慮樹結構的平衡問題，這將導致樹結構的depth無限增大，最壞情況是深度爲N。因此，我們可以對上一種算法進行改進，在每一次更改root的時候，判斷左邊樹和右邊樹的容量大小，始終令容量小的樹成爲容量大的樹的根節點的子樹。這種做法，將使樹結構的深度最大爲lg2(N)。當N很大的時候，樹結構的深度對比與上一種算法將大幅度降低，以此來提高程序效率。

Quick Union with Path Compression

基於Quick Union算法，另外一種改進則是，每次訪問一個點時，都將id[]里的儲存值改爲當前樹的根節點序號，大大減小樹的深度。

Weighted Quick Union with Path Compression

綜合上述兩種改進方法，可以形成最優解法。以下是最壞情況下算法的數組訪問次數。這裏的N，M表示對一個包含N個點的點集進行M次聯合操作。

應用-percolation

Union-Find的算法可以應用在判斷棋盤中最上排與最下排是否可以用白色方格連通。這種問題可以抽象爲下圖右邊的點連接問題。圖中有一個小小技巧，在最上排以上和最下排以下分別加入一個虛擬的頂點，這時問題就轉變爲判斷這兩個點連通與否。