在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然後按一定順序將屬於同一組的元素所在的集合合併，其間要反覆查找一個元素在哪個集合中。 如果n比較大，那麼反覆詢問你某個元素所在集合，你該怎麼做？ 如果每次都遍歷，那麼顯然會超時，那麼用一些數據結構比如建樹什麼的，很可 ...
在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然後按一定順序將屬於同一組的元素所在的集合合併，其間要反覆查找一個元素在哪個集合中。
如果n比較大，那麼反覆詢問你某個元素所在集合，你該怎麼做？
如果每次都遍歷，那麼顯然會超時，那麼用一些數據結構比如建樹什麼的，很可能會空間不夠，在這個時候就得用到並查集了。
顧名思義，並查集就是將相同集合的想辦法聯繫在一起，那樣查的時候就不用一一遍歷來詢問它是不是這個集合的了。
例題，暢通工程，大體題意：每行給你倆個數代表路的編號且這倆條路已聯通，最後問你還至少需要修幾條路使所有路都能夠聯通。
思路：給每一個聯通的集團設定一個老大，而集團成員都存儲老大的id，每進來倆相連的成員看他們老大是誰，如果是不同老大就改成相同老大，因為他們是相連的，是一個集團的，那最後看看有多少個老大，那就有多少個集團，那就需要多少條路將這些集團連起來。
若要這些集團連起來，只需一個集團的某一個和其他集團有聯繫就好了，看看實際操作代碼吧：
int f[MAX+1]; //申請一個數組存儲每個成員的老大id
for(int i=1;i<=MAX;i++)
f[i]=i; //初始化每個人的老大就是自己 初始化
int _find(int n) //尋找這個人的老大是誰
{ if(n!=f[n])
return _find(f[n]); 查詢
return n;
}
a=_find(a1); b=_find(b1); //新進來倆有聯繫的成員，分別查詢他們老大是誰
if(a!=b) //如果這倆人老大不同，分別屬於倆集團的 聯通
f[b]=a; //讓一方老大任另一方老大為老大，倆集團從此有聯繫，合併成一個集團，有共同的一個老大了
int sum=0; 回答題目問題
for(int i=1;i<=MAX;i++) //sum為現在有幾個老大，即有幾個集團，當然同意局面就是所有人都有一個老大，他們都存儲老大id，而老大自己存儲自己id。
if(f[i]==i)
sum++;
如果要問這倆人是不是一個集團的，直接看他倆老大是不是同一個人。（f[a]?f[b]）
這樣就是並查集的查詢，聯通，都搞定了。
當然我說的這麼簡單是已經壓縮過路徑的，就是所有人都存最終老大的id,而沒壓縮過路徑的就是人們都存它上司的id，問的時候由上司再問上司，直到老大，最後判斷這倆老大是不是同一人。
待續……
