在一些有n個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然後按一定順序将屬于同一組的元素所在的集合合并，其間要反複查找一個元素在哪個集合中。這一類問題其特點是看似并不複雜，但資料量極大，若用正常的資料結構來描述的話，往往在空間上過大，計算機無法承受；即使在空間上勉強通過，運作的時間複雜度也極高，根本就不可能在規定的運作時間（1～3秒）内計算出試題需要的結果，隻能用并查集來描述。
并查集（disjoint
set），即“不相交集合”，是一種樹型的資料結構，用于處理一些不相交集合（disjoint
sets）的合并及查詢問題。常常在使用中以森林來表示。集就是讓每個元素構成一個單元素的集合，也就是按一定順序将屬于同一組的元素所在的集合合并。
将編号分别為1…n的n個對象劃分為不相交集合，在每個集合中，選擇其中某個元素代表所在集合。
常見兩種操作：
合并兩個集合
查找某元素屬于哪個集合
用編号最小的元素标記所在集合；定義一個數組 set[1..n] ，其中set[i] 表示元素i 所在的集合；
查找 Θ(1)
合并 Θ(n)
對于“合并操作”，必須搜尋全部元素！有沒有可以改進的地方呢？
每個集合用一棵“有根樹”表示，定義數組 set[1..n]
set[i] = i , 則i表示本集合，并是集合對應樹的根
set[i] = j, j<>i, 則 j 是 i 的父節點.
查找 最壞情況Θ(n)
合并 Θ(1)
性能有無本質的改進？如何避免最壞情況呢？
方法：将深度小的樹合并到深度大的樹
實作：假設兩棵樹的深度分别為h1和h2, 則合并後的樹的高度h是:
max(h1,h2), if h1<>h2.
h1+1, if h1=h2.
效果：任意順序的合并操作以後，包含k個節點的樹的最大高度不超過lgk
優化後算法及效率：
查找 Θ(n)
思想：每次查找的時候，如果路徑較長，則修改資訊，以便下次查找的時候速度更快
步驟:
第一步，找到根結點
第二步，修改查找路徑上的所有節點，将它們都指向根結點
帶路徑壓縮的查找算法：
路徑壓縮示意圖:
<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1232" target="_blank">（hdoj1232）暢通工程</a>
某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目标是使全省任何兩個城鎮間都可以實作交通（但不一定有直接的道路相連，隻要互相間接通過道路可達即可）。問最少還需要建設多少條道路？
典型的并查集題目
算法：
判斷圖是否連通且無回路
如果待連接配接的兩點如果祖先節點相同，那麼就構成回路，不符合
如果不構成回路，但是有多個根節點，也不符合
題目大意：
給你一些操作，p後邊輸入四個值，分别代表一條線段的起點、終點坐标，
當輸入q時，後邊輸入一個整形值k，輸出第k條線段所在的集合中包含的線段的個數
思路：并查集+計算幾何線段相交
當輸入p時，判斷後邊輸入的線段的起點和終點時，判斷跟之前的線段有沒有相交，如果有相交，就merge（）合并，
如果輸入的是q時，就列印出目前線段所在集合的個數