第7章树和二叉树第11讲-并查集.pptxVIP

7.9并查集7.9.1什么叫并查集 例如：如果已经得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系就十分复杂。在这种情况下，就需要应用并查集。 为了将问题简化，将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，可以推出Marry和Ben是亲戚。/15 输入：第一部分以N，M开始。N为问题涉及的人的个数（1≤N≤20000）。这些人的编号为1，2，3，…， N。 下面有M行（1≤M≤1000000），每行有两个数ai、bi，表示已知ai和bi是亲戚。 第二部分以Q开始。以下Q行有Q个询问（1≤Q≤1000 000），每行为ci和di，表示询问ci和di是否为亲戚。 输出：对于每个询问ci、di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。 解决分类问题/15输入样例：10 7 //N=10，M=72 45 71 38 91 25 62 33 //Q=33 47 108 9 类似于离散数学中的等价类问题：给定一个集合U和一个等价关系R，产生具有等价关系的等价类。/15采用集合的思路求解输入关系分离集合初始状态{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}/15结果集合：{1，2，3，4}，{5，6，7}，{8，9}，{10}求解：3 4 ? 3、4在同一个集合中 ? Yes7 10 ? 7、10不在同一个集合中 ? No8 9 ? 8、9在同一个集合中 ? Yes/15 并查集的数据结构记录了一组分离的动态集合S={S1，S2，…，Sk}。 每个动态集合Si（1≤i≤k）通过一个“代表”加以标识，该代表即为所代表的集合中的某个元素。对于集合Si，选取其中哪个元素作为代表是任意的。/15 对于给定的编号为1～n的n个元素，x表示其中的一个元素，设并查集为S，并查集的实现需要支持如下运算： MAKE_SET(S，n)：初始化并查集S，即S={S1，S2，…，Sn}，每个动态集合Si（1≤i≤n）仅仅包含一个编号为i的元素，该元素作为集合Si的“代表”。FIND_SET(S，x)：返回并查集S中x元素所在集合的代表。 UNION(S，x，y)：在并查集S中将x和y两个元素所在的动态集合（例如Sx和Sy）合并为一个新的集合Sx∪Sy。7.9.2并查集的算法实现 用有根树来表示集合，树中的每个结点包含集合的一个成员，每棵树表示一个集合。　多个集合形成一个森林，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。 /15　　在并查集中，每个分离集合对应的一棵树，称为分离集合树。整个并查集也就是一棵分离集合森林。　4个集合{1，2，3，4}、{5，6，7}、{8，9}、{10}，分别以4、7、9和10表示对应集合的编号。 49732108561{8，9}集合{1，2，3，4}集合{5，6，7}集合{10}集合/15在一棵高度较低的树中查找根结点的编号（即该集合的代表）所花的时间较少，如何保证构造的分离集合树较低呢？两棵分离集合树A和B，高度分别为hA和hB，则若hAhB，应将B树作为A树的子树；否则，将A树作为B树的子树。总之，总是高度较小的分离集合树作为子树。得到的新的分离集合树C的高度hC，以B树作A树的子树为例：hC=MAX{hA，hB+1}。/15并查集采用顺序方法存储，结点的类型声明如下：typedef struct node{ int data; //结点对应人的编号 int rank; //结点秩，大致为树的高度 int parent; //结点对应双亲下标} UFSTree; //并查集树的结点类型/15（1）并查集树的初始化void MAKE_SET(UFSTree t[]，int n) //初始化并查集树{ int i; for (i=1;i=n;i++) { t[i].data=i; //数据为该人的编号 t[i].rank=0; //秩初