(HDUACM201209版-07)并查集(最小生成樹)

第七講并查集

（DisjointSet）導(dǎo)引問題 在某個城市里住著n個人，現(xiàn)在給定關(guān)于n個人的m條信息（即某2個人認(rèn)識），

假設(shè)所有認(rèn)識的人一定屬于同一個單位，請計算該城市最多有多少單位？如何實(shí)現(xiàn)？什么是并查集？英文：DisjointSet，即“不相交集合”將編號分別為1…N的N個對象劃分為不相交集合，在每個集合中，選擇其中某個元素代表所在集合。常見兩種操作：合并兩個集合查找某元素屬于哪個集合所以，也稱為“并查集”實(shí)現(xiàn)方法（1）用編號最小的元素標(biāo)記所在集合；定義一個數(shù)組set[1..n]，其中set[i]表示元素i所在的集合；iSet(i)不相交集合：{1,3,7},{4},{2,5,9,10},{6,8}方法(1)——效率分析find1(x){returnset[x];}Merge1(a,b){i=min(a,b);j=max(a,b);for(k=1;k<=N;k++){if(set[k]==j)set[k]=i;}}Θ(1)Θ(N)有待改進(jìn)？對于“合并操作”，必須搜索全部元素！樹結(jié)構(gòu)如何？實(shí)現(xiàn)方法（2）每個集合用一棵“有根樹”表示定義數(shù)組set[1..n]set[i]=i,則i表示本集合，并是集合對應(yīng)樹的根set[i]=j,j<>i,則j是i的父節(jié)點(diǎn).iSet(i法(2)——效率分析find2(x){r=x;while(set[r]!=r)r=set[r];returnr;}merge2(a,b){if(a<b)set[b]=a;elseset[a]=b;}Θ(1)最壞情況Θ(N)一般情況是…?困惑~~~性能有本質(zhì)改進(jìn)?如何避免最壞情況?避免最壞情況方法：將深度小的樹合并到深度大的樹實(shí)現(xiàn)：假設(shè)兩棵樹的深度分別為h1和h2,則合并后的樹的高度h是:max(h1,h2),ifh1<>h2.h1+1,ifh1=h2.效果：任意順序的合并操作以后，包含k個節(jié)點(diǎn)的樹的最大高度不超過優(yōu)化后算法及效率merge3(a,b){if(height(a)==height(b)){height(a)=height(a)+1;set[b]=a;}elseif(height(a)<height(b))set[a]=b;elseset[b]=a;}find2(x){r=x;while(set[r]!=r)r=set[r];returnr;}最壞情況Θ(logN)Θ(1)進(jìn)一步優(yōu)化——路徑壓縮思想：每次查找的時候，如果路徑較長，則修改信息，以便下次查找的時候速度更快步驟:第一步，找到根結(jié)點(diǎn)第二步，修改查找路徑上的所有節(jié)點(diǎn)，將它們都指向根結(jié)點(diǎn)帶路徑壓縮的查找算法find3(x){r=x;while(set[r]<>r)//循環(huán)結(jié)束，則找到根節(jié)點(diǎn)r=set[r];i=x;while(i<>r)//本循環(huán)修改查找路徑中所有節(jié)點(diǎn){j=set[i];set[i]=r;i=j;}

}路徑壓縮示意圖9108122021164611164111101298202116示例—暢通工程(HDOJ-1232)題目描述： 某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標(biāo)是使全省任何兩個城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達(dá)即可）。問最少還需要建設(shè)多少條道路？題目分析最赤裸裸的并查集，無話可說～附:參考源碼(HDOJ-1232)#include"stdio.h"intbin[1002];intfindx(intx){intr=x;while(bin[r]!=r)r=bin[r];returnr;}voidmerge(intx,inty){intfx,fy;fx=findx(x);fy=findx(y);if(fx!=fy)bin[fx]=fy;}intmain(){intn,m,i,x,y,count;while(scanf("%d",&n),n){for(i=1;i<=n;i++)bin[i]=i;for(scanf("%d",&m);m>0;m--){scanf("%d%d",&x,&y);merge(x,y);}for(count=-1,i=1;i<=n;i++)if(bin[i]==i)count++;printf("%d\n",count);}}示例—小希的迷宮(HDOJ-1272)題目鏈接

下面的例子，前兩個是符合條件的，但是最后一個卻有兩種方法從5到達(dá)8。

題目分析:該你們來說了～經(jīng)典應(yīng)用——最小生成樹1、什么是——生成樹？564231165346526556423115465a.帶權(quán)圖b.生成樹經(jīng)典應(yīng)用——最小生成樹2、什么是——最小生成樹？5642311653465265a.帶權(quán)圖c.最小生成樹56423115342經(jīng)典應(yīng)用——最小生成樹3、如何求——最小生成樹？A)Prim算法B)Kruskal算法理論基礎(chǔ)：MST性質(zhì)（證明…）經(jīng)典應(yīng)用——最小生成樹4、Kruskal算法步驟：5642311653465265a.帶權(quán)圖一、把原始圖的N個節(jié)點(diǎn)看成N個獨(dú)立子圖；二、每次選取當(dāng)前最短的邊（前提操作是？），看兩端是否屬于不同的子圖；若是，加入；否則，放棄；三、循環(huán)操作該步驟二，直到有N－1條邊；1經(jīng)典應(yīng)用——最小生成樹5、算法過程示意：5642311653465265原始圖5642316534652651經(jīng)典應(yīng)用——最小生成樹5、算法過程示意：5642311653465265原始圖5642316534652651經(jīng)典應(yīng)用——最小生成樹5、算法過程示意：5642311653465265原始圖5642316534652651經(jīng)典應(yīng)用——最小生成樹5、算法過程示意：5642311653465265原始圖5642316534652651經(jīng)典應(yīng)用——最小生成樹5、算法過程示意：5642311653465265原始圖5642316534652651經(jīng)典應(yīng)用——最小生成樹5、算法過程示意：5642311653465265原始圖5642316534