acm程序設(shè)計杭電課件-并查集

1、ACM程序設(shè)計杭州電子科技大學(xué) 劉春英 這一周，你 了嗎？AC每周一星（5）：06092709朱衛(wèi)江 第六講并查集（Disjoint Set）導(dǎo)引問題在某個城市里住著n個人，任何兩個認(rèn)識的人不是朋友就是敵人，而且滿足：我朋友的朋友是我的朋友；我敵人的敵人是我的朋友；已知關(guān)于 n個人的m條信息（即某2個人是朋友或者敵人），假設(shè)所有是朋友的人一定屬于同一個團(tuán)伙，請計算該城市最多有多少團(tuán)伙？如何實現(xiàn)？什么是并查集？英文：Disjoint Set，即“不相交集合”將編號分別為1N的N個對象劃分為不相交集合，在每個集合中，選擇其中某個元素代表所在集合。常見兩種操作：合并兩個集合查找某元素屬于哪個集合所以

2、，也稱為“并查集”實現(xiàn)方法（1）用編號最小的元素標(biāo)記所在集合；定義一個數(shù)組 set1.n ，其中seti 表示元素i 所在的集合；123456789101214261622iSet(i)不相交集合： 1,3,7, 4, 2,5,9,10, 6,8方法(1)效率分析find1(x) return setx;Merge1(a,b) i = min(a,b); j = max(a,b); for (k=1; k=N; k+) if (setk = j) setk = i; (1)(N)有待改進(jìn)？對于“合并操作”，必須搜索全部元素！樹結(jié)構(gòu)如何？實現(xiàn)方法（2）每個集合用一棵“有根樹”表示定義數(shù)組 set

3、1.nseti = i , 則i表示本集合，并是集合對應(yīng)樹的根seti = j, ji, 則 j 是 i 的父節(jié)點. 123456789101232134334iSet(i法(2)效率分析find2(x) r = x; while (setr != r) r = setr; return r;merge2(a, b) if (ab) setb = a; else seta = b;(1)最壞情況(N)一般情況是?困惑性能有本質(zhì)改進(jìn)?如何避免最壞情況?避免最壞情況方法：將深度小的樹合并到深度大的樹實現(xiàn)：假設(shè)兩棵樹的深度分別為h1和h2, 則合并后的樹的高度h是:max(

4、h1,h2), if h1h2.h1+1, if h1=h2.效果：任意順序的合并操作以后，包含k個節(jié)點的樹的最大高度不超過優(yōu)化后算法及效率merge3(a,b) if (height(a) = height(b) height(a) = height(a) + 1; setb = a; else if (height(a) height(b) seta = b; else setb = a; find2(x) r = x; while (setr != r) r = setr; return r;最壞情況(log N)(1)進(jìn)一步優(yōu)化路徑壓縮思想：每次查找的時候，如果路徑較長，則修改信息，以

5、便下次查找的時候速度更快步驟:第一步，找到根結(jié)點第二步，修改查找路徑上的所有節(jié)點，將它們都指向根結(jié)點帶路徑壓縮的查找算法find3(x) r = x; while (setr r) /循環(huán)結(jié)束，則找到根節(jié)點 r = setr; i = x; while (i r) /本循環(huán)修改查找路徑中所有節(jié)點 j = seti; seti = r; i = j; 路徑壓縮示意圖9108122021164611164111101298202116示例暢通工程(HDOJ-1232)題目描述：某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標(biāo)是使全省任何兩個城

6、鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達(dá)即可）。問最少還需要建設(shè)多少條道路？ 題目分析最赤裸裸的并查集，無話可說示例小希的迷宮(HDOJ-1272)題目鏈接下面的例子，前兩個是符合條件的，但是最后一個卻有兩種方法從5到達(dá)8。 題目分析:該你們來說了Any question?相關(guān)練習(xí)附加題目：HDOJ-1558Segment set HDOJ-1811Rank of Tetris HDOJ-1829A Bugs Life HDOJ-1198Farm Irrigation 2008ACM ProgrammingExercise(6)_并查集 附:參考源碼(HDOJ-1232)#include stdio.hint bin1002;int findx(int x) int r=x; while(binr !=r) r=binr; return r;void merge(int x,int y) int fx,fy; fx = findx(x); fy = findx(y); if(fx != fy) binfx = fy;int main() int n,m,i,x,y,count; while(scanf(%d,&n),n) for(i=1;i0;m-) scanf(%d %d,&x,&y)