例如：如果已經(jīng)得到完整的家譜，判斷兩個人是否親戚應該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗親戚關系就十分復雜。在這種情況下，就需要應用并查集。為了將問題簡化，將得到一些親戚關系的信息，如Marry和Tom是親戚，Tom和Ben是親戚，等等。從這些信息中，可以推出Marry和Ben是親戚。7.9.1什么叫并查集7.9并查集1/15輸入：第一局部以N，M開始。N為問題涉及的人的個數(shù)〔1≤N≤20000〕。這些人的編號為1，2，3，…，N。下面有M行〔1≤M≤1000000〕，每行有兩個數(shù)ai、bi，表示ai和bi是親戚。第二局部以Q開始。以下Q行有Q個詢問〔1≤Q≤1000000〕，每行為ci和di，表示詢問ci和di是否為親戚。輸出：對于每個詢問ci、di，輸出一行：假設ci和di為親戚，那么輸出“Yes〞，否那么輸出“No〞。解決分類問題2/15輸入樣例：107 //N=10，M=7245713891256233 //Q=33471089類似于離散數(shù)學中的等價類問題：給定一個集合U和一個等價關系R，產生具有等價關系的等價類。3/15采用集合的思路求解輸入關系別離集合初始狀態(tài){1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}，{9}，{10}〔2，4〕{1}，{2，4}，{3}，{5}，{6}，{7}，{8}，{9}，{10}〔5，7〕{1}，{2，4}，{3}，{5，7}，{6}，{8}，{9}，{10}〔1，3〕{1，3}，{2，4}，{5，7}，{6}，{8}，{9}，{10}〔8，9〕{1，3}，{2，4}，{5，7}，{6}，{8，9}，{10}〔1，2〕{1，2，3，4}，{5，7}，{6}，{8，9}，{10}〔5，6〕{1，2，3，4}，{5，6，7}，{8，9}，{10}〔2，3〕{1，2，3，4}，{5，6，7}，{8，9}，{10}4/15{1，2，3，4}，{5，6，7}，{8，9}，{10}34

3、4在同一個集合中Yes求解：710

7、10不在同一個集合中No89

8、9在同一個集合中Yes結果集合：5/15并查集的數(shù)據(jù)結構記錄了一組別離的動態(tài)集合S={S1，S2，…，Sk}。每個動態(tài)集合Si〔1≤i≤k〕通過一個“代表〞加以標識，該代表即為所代表的集合中的某個元素。對于集合Si，選取其中哪個元素作為代表是任意的。6/157對于給定的編號為1～n的n個元素，x表示其中的一個元素，設并查集為S，并查集的實現(xiàn)需要支持如下運算：MAKE_SET(S，n)：初始化并查集S，即S={S1，S2，…，Sn}，每個動態(tài)集合Si〔1≤i≤n〕僅僅包含一個編號為i的元素，該元素作為集合Si的“代表〞。FIND_SET(S，x)：返回并查集S中x元素所在集合的代表。UNION(S，x，y)：在并查集S中將x和y兩個元素所在的動態(tài)集合〔例如Sx和Sy〕合并為一個新的集合Sx∪Sy。

用有根樹來表示集合，樹中的每個結點包含集合的一個成員，每棵樹表示一個集合。多個集合形成一個森林，以每棵樹的樹根作為集合的代表，并且根結點的父結點指向其自身，樹上的其他結點都用一個父指針表示它的附屬關系。

7.9.2并查集的算法實現(xiàn)8/15在并查集中，每個別離集合對應的一棵樹，稱為別離集合樹。整個并查集也就是一棵別離集合森林。4個集合{1，2，3，4}、{5，6，7}、{8，9}、{10}，分別以4、7、9和10表示對應集合的編號。4321{1，2，3，4}集合756{5，6，7}集合98{8，9}集合10{10}集合9/15在一棵高度較低的樹中查找根結點的編號〔即該集合的代表〕所花的時間較少，如何保證構造的別離集合樹較低呢？兩棵別離集合樹A和B，高度分別為hA和hB，那么假設hA>hB，應將B樹作為A樹的子樹；否那么，將A樹作為B樹的子樹。總之，總是高度較小的別離集合樹作為子樹。得到的新的別離集合樹C的高度hC，以B樹作A樹的子樹為例：hC=MAX{hA，hB+1}。10/15typedefstructnode{intdata; //結點對應人的編號intrank; //結點秩，大致為樹的高度intparent; //結點對應雙親下標}UFSTree; //并查集樹的結點類型并查集采用順序方法存儲，結點的類型聲明如下：11/15〔1〕并查集樹的初始化voidMAKE_SET(UFSTreet[]，intn)//初始化并查集樹{inti;for(i=1;i<=n;i++){ t[i].data=i; //數(shù)據(jù)為該人的編號 t[i].rank=0; //秩初始化為0 t[i].parent=i; //雙親初始化指向自已}}12/15〔2〕查找一個元素所屬的集合intFIND_SET(UFSTreet[]，intx)//在x所在子樹中查找集合編號{if(x!=t[x].parent) //雙親不是自已 return(FIND_SET(t，t[x].parent));//遞歸在雙親中找x

else return(x); //雙親是自已，返回x}13/1514/15〔3〕兩個元素各自所屬的集合的合并voidUNION(UFSTreet[]，intx，inty)//將x和y所在的子樹合并{x=FIND_SET(t，x); //查找x所在別離集合樹的編號y=FIND_SET(t，y); //查找y所在別離集合樹的編號if(t[x].rank>t[y].rank) //y結點的秩小于x結點的秩 t[y].parent=x; //將y連到x結點上，x作為y的雙親結點else //y結點的秩大于等于x結點的秩{ t[x].parent=y; //將x連到y(tǒng)結