查并交集算法讲.ppt

亲戚—一个查并交集的应用信安0801郭海蓉问题描述若x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。先初始化一系列亲戚关系,最后对输入的任意两个人a和b,判断他们是不是亲戚关系。第一行:三个整数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是否具有亲戚关系。解题思路<一>可以将a、b两个人分别看作一个点,a与b有亲戚关系表示为a到b有一条路径(没有方向)。因此,所有人之间的关系可以用一个邻接矩阵来存储和表示。那么最后要求的任意两个人是否是亲戚关系就转化为求一个点到另一个点是否可达,至此,不难想到传统的Horspool算法即可解决这个问题。但由于题目中的数据比较大(5000),而Horspool算法时间复杂度达到O(n^3),因此,该方法不可行解题思路<二>用集合的观点来解决该题。初始时每一个人代表一个集合,经过建立几组亲戚关系,将有亲戚关系的人合并到一个集合,每增加一组亲戚关系,就将这些亲戚所在集合进行合并,直到最后只剩几个相对大的集合。所求问题就转化为对这些集合的查找,如果两个人在同一个集合,那么他们是亲戚关系,否则不是。数据结构为了实现集合的查找与合并,有两个函数不可以,亦即Find_Set(intn)、voidUnion_Set(inta,intb)Find_Set(intn):查找n所在集合的根结点,即集合代表voidUnion_Set(inta,intb):将结点a、b所在集合进行合并虽然每一个子集合我们可以理解为用一棵树代表,所有集合表示一个森林,但这里我用线性表即数组存储各元素算法描述(伪代码)算法Find_Set(intn)//查找n所在集合的根结点,即集合代表ifArray[n]=n//双亲结点就是它本身returnn;else returnFind_Set(Array[n]);//否则不断递归查找其双亲结点算法Union_Set(inta,intb)//将结点a、b所在集合进行合并intx←Find_Set(a);//查找a所在集合的根结点inty←Find_Set(b);//查找b所在集合的根结点Ifx<yArray[y]←x;//将根结点小的作为根结点大的子结点elseArray[x]←y;算法实现#include<iostream>#include<algorithm>usingnamespacestd;intArray[5002];intFind_Set(intt)//不断递归找到结点t的双亲结点,直到找到t所在集合的根结点,即集合的代表{ if(Array[t]==t)//双亲就是它本身 returnt; else returnFind_Set(Array[t]);}voidUnion_Set(inta