HDUACM版06并查集最小生成树

1、ACM2第六讲第六讲并查集并查集（Disjoint Set）3导引问题在某个城市里住着n个人，现在给定关于 n个人的m条信息（即某2个人认识），假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？4什么是并查集？英文：Disjoint Set，即“不相交集合”将编号分别为1N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：n合并并两个集合n查查找某元素属于哪个集合所以，也称为“并查集”5实现方法（1）n用编号最小的元素标记所在集合；n定义一个数组 set1.n ，其中seti 表示元素i 所在的集合；123456789101214261622i

2、Set(i)不相交集合： 1,3,7, 4, 2,5,9,10, 6,86方法(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)7有待改进？n对于“合并操作”，必须搜索全部元素！n树结构如何？8实现方法（2）n每个集合用一棵“有根树”表示n定义数组 set1.nnseti = i , 则i表示本集合，并是集合对应树的根nseti = j, ji, 则 j 是 i 的父节点. 1234567891012321343

3、34iSet(i)152471036899方法(2)效率分析find2(x) r = x; while (setr != r) r = setr; return r;merge2(a, b) if (ab) setb = a; else seta = b;(1)最坏情况(N)一般情况是?10困惑n性能有本质改进?n如何避免最坏情况?11避免最坏情况n方法：将深度小的树合并到深度大的树n实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是:nmax(h1,h2), if h1h2.nh1+1, if h1=h2.n效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过klg1

4、2优化后算法及效率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)13进一步优化路径压缩n思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快n步骤:n第一步，找到根结点n第二步，修改查找路径上的所有节点，将它们都指向根结点14带路径

5、压缩的查找算法nfind3(x)nn r = x;n while (setr r) /循环结束，则找到根节点n r = setr; n i = x;n while (i r) /本循环修改查找路径中所有节点n n j = seti;n seti = r;n i = j;n 15路径压缩示意图91081220211646111641111012982021 1616示例示例畅通工程畅通工程(HDOJ-1232)n题目描述：题目描述：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连

6、，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ 17题目分析n最赤裸裸的并查集，无话可说18附:参考源码(HDOJ-1232)n#include stdio.hnint bin1002;nint findx(int x)nn int r=x;n while(binr !=r)n r=binr;n return r;nnvoid merge(int x,int y)nn int fx,fy;n fx = findx(x);n fy = findx(y);n if(fx != fy)n binfx = fy;nnint main()nn int n,m,i,x,y,count;n

7、while(scanf(%d,&n),n)n n for(i=1;i0;m-)n n scanf(%d %d,&x,&y);n merge(x,y);n n for(count=-1, i=1;i=n;i+)n if(bini = i)n count +;n printf(%dn,count);n n19示例小希的迷宫(HDOJ-1272)n题目链接下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。 20经典应用最小生成树n1 1、什么是什么是生成树？生成树？564231165346526556423115465a.带权图b.生成树21经典应用最小生成

8、树n2 2、什么是什么是最小生成树？最小生成树？5642311653465265a.带权图c.最小生成树5642311534222经典应用最小生成树n3 3、如何求、如何求最小生成树？最小生成树？nA) Prim A) Prim 算法算法nB) KruskalB) Kruskal算法算法n理论基础：理论基础：MSTMST性质（证明性质（证明）23经典应用最小生成树n4 4、KruskalKruskal算法步骤：算法步骤：5642311653465265a.带权图一、把原始图的N个节点看成N个独立子图；二、每次选取当前最短的边（前提操作是？），看两端是否属于不同的子图；若是，加入；否则，放弃；三

9、、循环操作该步骤二，直到有N1条边；241经典应用最小生成树n5 5、算法过程示意：、算法过程示意：5642311653465265原始图564231653465265251经典应用最小生成树n5 5、算法过程示意：、算法过程示意：5642311653465265原始图564231653465265261经典应用最小生成树n5 5、算法过程示意：、算法过程示意：5642311653465265原始图564231653465265271经典应用最小生成树n5 5、算法过程示意：、算法过程示意：5642311653465265原始图564231653465265281经典应用最小生成树n5 5、算法过程示意：、算法过程示意：5642311653465265原始图564231653465265291经典应用最小生成树n5 5、算法过程示意：、算法过程示意：5642311653465265原始图