如果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[a]=b; //讓一方老大任另一方老大為老大，倆集團從此有聯系，合並成一個集團，有共同的一個老大了
//_find(a); } //下面壓縮路徑時加這句進行壓縮
int sum=0; 回答題目問題
for(int i=1;i<=MAX;i++) //sum為現在有幾個老大，即有幾個集團，當然統一局面就是所有人都有一個老大，他們都存儲自己上司id，而老大自己存儲自己id。
if(f[i]==i)
sum++;
如果要問這倆人是不是一個集團的，直接看他倆老大是不是同一個人。（_find(a)?_find(b)）
這樣就是並查集的查詢，聯通，都搞定了。
當然我說的這麼簡單是沒有壓縮過路徑的，就是所有人都存自己上司的id,尋找老大時需要由上司再問上司，直到老大（老大的特點是存儲自己id）,而壓縮過路徑的就是人們都存它老大的id，問的時候直接看倆人存儲的id是否相同（f[a]?f[b]）。
壓縮路徑得加這段代碼，很容易看懂的,就在尋找函數上加點就好了：
int _find(int n)
{ int res=n;
while(n!=f[n])
n=f[n]; //找到老大id
int j;
while(res!=n)
{ j=f[res];
f[res]=n; //把從自己開始把上司id都改成老大id
res=j;}
return n; //返回老大
}
待續……
