第1章　實用數據結構

1.1　并查集

若某個部落過于龐大，則部落成員見面也有可能不認識。已知某個部落的成員關系圖，任意給出其中兩個人，判斷是否有親戚關系。規定：①若x、y是親戚，y和z是親戚，則x和z也是親戚；②若x、y是親戚，則x的親戚也是y的親戚，y的親戚也是x的親戚。

如何才能快速判斷兩個人是否有親戚關系呢？以上規定中的第①條是傳遞關系，第②條相當于兩個集合的合并，因此對該問題可以采用并查集輕松解決。并查集是一種樹形數據結構，用于處理集合的合并及查詢問題。

1. 算法步驟

（1）初始化。將每個節點所在的集合號都初始化為其自身編號。

（2）查找。查找兩個元素所在的集合，即找祖宗。查找時，采用遞歸的方法找其祖宗，找到祖宗（集合號等于自身）時停止；然后回歸，回歸時將祖宗到當前節點路徑上的所有節點都統一為祖宗的集合號。

（3）合并。若兩個節點的集合號不同，則將兩個節點合并為一個集合，合并時只需將一個節點的祖宗集合號修改為另一個節點的祖宗集合號。擒賊先擒王，只改祖宗即可！

2. 完美圖解

假設現在有7個人，首先輸入親戚關系圖，然后判斷兩個人是否有親戚關系。

（1）初始化。

（2）查找。輸入親戚關系2、7，查找到2的集合號為2，7的集合號為7。

（3）合并。兩個元素的集合號不同，將兩個元素合并為一個集合。在此約定將小的集合號賦值給大的集合號，因此修改fa[7]=2。

（4）查找。輸入親戚關系4、5，查找到4的集合號為4，5的集合號為5。

（5）合并。兩個元素的集合號不同，將兩個元素合并為一個集合，修改fa[5]=4。

（6）查找。輸入親戚關系3、7，查找到3的集合號為3，7的集合號為2。

（7）合并。兩個元素的集合號不同，將兩個元素合并為一個集合，修改fa[3]=2。

（8）查找。輸入親戚關系4、7，查找到4的集合號為4，7的集合號為2。

（9）合并。兩個元素的集合號不同，將兩個元素合并為一個集合，修改fa[4]=2。擒賊先擒王，只改祖宗即可！有兩個節點的集合號為4，只需修改兩個節點中的祖宗，無須將集合號為4的所有節點都檢索一遍，這正是并查集的巧妙之處！

（10）查找。輸入親戚關系3、4，查找到3的集合號為2，4的集合號為2。

（11）合并。兩個元素的集合號相同，無須合并。

（12）查找。輸入親戚關系5、7，查找到7的集合號為2，查找到5的集合號不等于5，所以找5的祖宗。首先找到其父節點4，4的父節點為2，2的集合號等于2（祖宗），搜索停止。返回時，將祖宗到當前節點路徑上所有節點的集合號都統一為祖宗的集合號。更新5的集合號為祖宗的集合號2。

（13）合并。兩個元素的集合號相同，無須合并。

（14）查找。輸入親戚關系5、6，查找到5的集合號為2，6的集合號為6。

（15）合并。兩個元素的集合號不同，將兩個元素合并為一個集合，修改fa[6]=2。

（16）查找。輸入親戚關系2、3，查找到2的集合號為2，3的集合號為2。

（17）合并。兩個元素的集合號相同，無須合并。

（18）查找。輸入親戚關系1、2，查找到1的集合號為1，2的集合號為2。兩個元素的集合號不同，將兩個元素合并為一個集合，修改fa[2]=1。

假設到此為止，親戚關系圖已經輸入完畢。可以看到3、4、5、6、7這些節點的集合號并沒有被修改為1，這樣做真的可以嗎？現在，若判斷5和2是不是親戚關系，則過程如下。

（1）查找到5的集合號為2，5的集合號不等于5，找其祖宗。首先查找到5的父節點2，2的父節點1，1的集合號為1（祖宗），搜索停止。將祖宗1到5這條路徑上所有節點的集合號都更新為1。

（2）查找到2的集合號為1，找其祖宗。2的祖宗為1，1的集合號為1（祖宗），搜索停止。將祖宗1到2這條路徑上所有節點的集合號都更新為1。

（3）5和2的集合號都為1，因此5和2是親戚關系。

3. 算法實現

（1）初始化。將節點i的集合號初始化為其自身編號。

（2）查找。查找兩個元素所在的集合，即找祖宗。查找時，采用遞歸的方法找其祖宗（集合號等于自身）。回歸時，將祖宗到當前節點路徑上的所有節點都統一為祖宗的集合號。

fa[x]表示x的集合號，若x!=fa[x]，則說明x節點不是祖宗。繼續向上找，找到祖宗后返回。回歸時將祖宗到當前節點路徑上的所有節點都統一為祖宗的集合號，如下圖所示。

（3）合并。先找到x的集合號a，y的集合號b，若a和b相等，則無須合并。若a和b不相等，則將a的集合號修改為b，或者將b的集合號修改為a。擒賊先擒王，只改祖宗即可！

輸入1和8的親戚關系，先找到1的祖宗2，8的祖宗6，將6的集合號修改為2即可。

4. 算法分析

若有n個節點、e條邊（關系），則每條邊（u, v）進行集合合并時，都要查找u和v的祖宗，查找的路徑為從當前節點一直到根節點，n個節點組成的樹的平均高度為logn，因此并查集中，合并集合的時間復雜度為O(elogn)。