最新并查集教学讲义PPT.ppt

《最新并查集教学讲义PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并查集并查集是一种树型的高级数据结构，主要用于处理不相交集合的合并及查询问题。它在计算机科学中有着广泛的应用，例如求解最小生成树、亲戚关系的判定、确定无向图的连通子图个数、最小公共祖先问题等，都要用到并查集。集合集合是数学中最基本的构造之一，将一组满足某种性质的对象放在一起就形成了集合。集合中包含的对象称为集合中的元素，集合中的元素是无序而且唯一的。人们常用大写英文字母A、B、C等来表示集合,并用x∈A来表示x是集合A中的元素。还可以用vector.它有数组的优点，而且又不必考虑数组那样可能越界的情况。并查集的概念在某些应用中，我们要检查两个元素是否属于同一个集合，或者将两个不同的

2、集合合并为一个集合。这是不相交集合经常处理的两种操作：查找和合并,我们称为并查集。查找find：查找一个指定元素属于哪个集合。对于判断两个元素是否属于同一个集合是非常有用的。合并union：将两个集合合并为1个集合。除了这两个操作之外，还有一个基础的操作——makeset,用于建立只有1个元素的集合。为了更精确的定义上述三个操作，我们需要用一种方法来表示集合。一种通用的做法是选择集合中某个固定的元素作为集合的代表，让他唯一的标识整个集合。一般说来，选取的代表是任意的。也就是说，到底选取集合中的哪个元素作为它的代表是无关紧要的。在并查集中，我们对于集合的表示利用树的思想，一个集合可以

3、看做一棵树，树根即代表该集合的标识。如果两个元素在同一个树中，则它们是同一个集合;合并两个集合，即是对两棵树进行合并。find(x):返回元素x所属集合的代表。为了判断任意两个元素x和y是否属于同一个集合，我们只需要判断find(x)和find(y)是否相等即可，如果相等，说明他们属于同一个集合，否则他们不属于同一个集合。union(x,y):将包含元素x的集合（假设为Sx）和包含元素y的集合（假设为Sy）合并为一个新的集合（即这两个集合的并集），所得到并集可以用它的任何一个元素来做代表，但在实践中，一般都是选择Sx或Sy的代表作为并集的代表。makeset(x):建立一个只包含元

4、素x的集合，显然，此时该集合的代表应该而且只能为x.并查集的实现：（数组）voidmakeset(x){parent[x]=-1;}parent[x]表示x的父亲编号.最开始的，每个元素自成一个集合，即每个元素开始都当做一棵树，其父亲节点初始为-1,表示它没有父亲。intfind(x)//查找x所在的集合。{while(parent[x]!=-1)x=parent[x];returnx;}voidmyunion(intx,inty){intr1=find(x);intr2=find(y);if(height[r1]>height[r2])num[r2]=r1;elseif(heig

5、ht[r1]

6、d(intx){if(parent[x]!=-1)parent[x]=find(parent[x]);if(parent[x]==-1)returnx;elsereturnparent[x];}这是路径压缩。它可以在find的过程中，让路径上的元素都成为根的儿子节点。这样，从形式上看，树就从细长型变成了扁平型。并查集的应用实例亲戚若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。第一行：三个

7、整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。输出格式P行，每行一个'Yes'或'No'。表示第i个询问的答案为“具有”或“不具有”亲戚关系。简单的并查集题目。动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A