数据结构之并查集（一）

并查集Disjoint Set UnionDSU是算法竞赛和面试中非常经典的数据结构它实现简单但思想巧妙。举个例子开学了若干名同学齐聚校园。一开始同学们都互不认识都是独立的个体。如果A同学和B同学成为了好朋友那么他们就构成了一个朋友圈如果A同学又和C同学成为了好朋友那么C同学也加入了这个朋友圈和B同学也有了联系。并查集就是用来高效管理这种分组关系的工具主要解决两个问题合并Union把两个人所在的组合并成一个组查询Find判断两个人是否在同一个组里并查集是用树结构来表示两点之间是否有联系如果两个点在同一棵树上那么两个点就有关系否则就没关系。但是这个树结构并不依赖建边而是用一个父节点数组father来表示其中father[i]的元素值为节点i的父节点。那么如果father[i]的值为i说明点i就是树的根节点。然后就是3个函数init()初始化函数Union()合并函数Find()查找根节点函数。了解了这3个函数的作用之后并查集的问题就很简单了初始化时调用init()函数合并时调用Union()函数找根节点时调用Find()函数即可。voidinit(intnum){//初始化f[i]i一开始每个点都是独立的for(inti1;inum;i){father[i]i;}}intFind(intx){//返回x所在树的根节点if(x!father[x]){//如果x不是根节点returnFind(father[x]);//递归父节点去找根节点}else{returnx;//如果是返回根节点}}voidUnion(intx,inty){//将点x和点y合并intfxFind(x);//找到x的根节点intfyFind(y);//找到y的根节点if(fx!fy){//如果两个根节点不相同说明两个点在两棵树上father[fx]fy;//根节点合并直接合并两棵树}}例题1洛谷P1551 亲戚题目描述若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。规定xxx和yyy是亲戚yyy和zzz是亲戚那么xxx和zzz也是亲戚。如果xxxyyy是亲戚那么xxx的亲戚都是yyy的亲戚yyy的亲戚也都是xxx的亲戚。输入格式第一行三个整数n,m,pn,m,pn,m,pn,m,p≤5000n,m,p \le 5000n,m,p≤5000分别表示有nnn个人mmm个亲戚关系询问ppp对亲戚关系。以下mmm行每行两个数MiM_iMi​MjM_jMj​1≤Mi, Mj≤n1 \le M_i,~M_j\le n1≤Mi​,Mj​≤n表示MiM_iMi​和MjM_jMj​具有亲戚关系。接下来ppp行每行两个数Pi,PjP_i,P_jPi​,Pj​询问PiP_iPi​和PjP_jPj​是否具有亲戚关系。输出格式ppp行每行一个Yes或No。表示第iii个询问的答案为“具有”或“不具有”亲戚关系。输入输出样例 #1输入 #16 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6输出 #1Yes Yes No#includeiostreamusingnamespacestd;constintN5e310;intn,m,p,father[N],u,v;voidinit(intnum){//初始化f[i]i一开始每个点都是独立的for(inti1;inum;i){father[i]i;}}intFind(intx){//返回x所在树的根节点if(x!father[x]){//如果x不是根节点returnFind(father[x]);//递归父节点去找根节点}else{returnx;//如果是返回根节点}}voidUnion(intx,inty){//将点x和点y合并intfxFind(x);//找到x的根节点intfyFind(y);//找到y的根节点if(fx!fy){//如果两个根节点不相同说明两个点在两棵树上father[fx]fy;//根节点合并直接合并两棵树}}intmain(){cinnmp;init(n);while(m--){cinuv;Union(u,v);//合并uv两点}while(p--){cinuv;if(Find(u)Find(v)){//如果u的根节点和v的根节点相同coutYesendl;//说明在同一棵树上}else{coutNoendl;//不在}}return0;}在这个基础版本的并查集上还有两个优化1.路径压缩在Find函数里只是在找根节点不妨把找到的根节点直接赋值到father[x]中直接指向根节点避免了后续反复递归调用。例如1的父节点是22的父节点是33的父节点是44 是根节点即father[1]2father[2]3father[3]4father[4]4那么Find()函数调用时不妨让father[1]直接为4后续再找1的祖先时就能减少很多次递归2.按秩合并规模较小的集合合并到规模较大的集合即较矮的树合并到较高的树里减少层次。需要建立一个Rank数组Rank[i]为点i的高度。#includeiostreamusingnamespacestd;constintN5e310;intn,m,p,father[N],u,v,Rank[N];voidinit(intnum){//初始化f[i]i一开始每个点都是独立的for(inti1;inum;i){father[i]i;Rank[i]1;}}intFind(intx){//返回x所在树的根节点if(x!father[x]){//如果x不是根节点returnfather[x]Find(father[x]);//递归父节点去找根节点}else{returnx;//如果是返回根节点}}voidUnion(intx,inty){//将点x和点y合并intfxFind(x);//找到x的根节点intfyFind(y);//找到y的根节点if(fxfy){//如果两个根节点不相同说明两个点在两棵树上return;}// 如果x的根和y的根是不同的那么就让x和y按高度合并if(Rank[fx]Rank[fy]){father[fx]fy;}elseif(Rank[fx]Rank[fy]){father[fy]fx;}else{father[fy]fx;Rank[fx]1;}}intmain(){cinnmp;init(n);while(m--){cinuv;Union(u,v);//合并uv两点}while(p--){cinuv;if(Find(u)Find(v)){//如果u的根节点和v的根节点相同coutYesendl;//说明在同一棵树上}else{coutNoendl;//不在}}return0;}