并查集总结
暑期专题一
前面一段时间复习了一下并查集这个东西,其实原本初一有学过一点但是当时没怎么听懂,现在重新回过头看就很好理解了。
并查集可以处理不相交集合的问题,这里说的有点不容易懂,可以用一道例题说明。
【例1】
有n个人,其中有m对人有血缘关系,我们要问q个问题,每个问题问任意两个人是否是亲戚(亲戚指的是直接或间接有血缘关系的人)
这道题是并查集最简单的情况,用到并查集最基本,也是一定会用到的两个功能:查找和合并。
首先并查集构成了一个森林,在例1里面在同一棵树里的人都互为亲戚,当然这里没有所谓的辈分之称,所以后面提到的祖先也只表示这棵树的根节点。
我们定义father[i]为编号为i的节点的父亲,并且定义当father[i]=-1时,i为整棵树的根节点。
首先是并查集第一个功能:查找。
对于例1的问题,我们只要查找两个人的祖先是否是同一个人就可以知道他们是否互为亲戚。
函数getfather(i)返回编号为i的节点的根节点编号,具体实现分递归和非递归方式,当然两种方式的速度差不多,大家可以根据自己的喜好和实际情况选择合适的实现方法,这里只给出递归的方式。
function getfather(i:longint):longint; begin if father[i]=-1 then exit(i) else exit(getfather(father[i])); end;
像上面的这种实现方式在树的深度较大时效率很低,所以我们可以使用一个叫做“路径压缩(su)”的方法,具体是得到i节点的祖先后,直接把i的父亲变成祖先,那么以后再次查找时就快很多了,而实现也是相当简单,只需要稍微改动代码即可:
function getfather(i:longint):longint; begin if father[i]=-1 then exit(i) else father[i]:=getfather(father[i]); exit(father[i]); end;
接下来就是并查集的第二个功能:合并。
在例1中,得到一对新的血缘关系后,如果他们是亲戚,无视即可,如果他们不是亲戚,就将他们的祖先合并。
代码如下:
procedure union(p,q:longint); var x,y:longint; begin x:=gf(p); y:=gf(q); if x=y then exit; f[x]:=y; end;
当然,合并的方法也可以适当优化,毕竟到底将x变成y的父亲还是y变成x的父亲是值得研究的,我们可以用启发式的合并:按秩合并。
秩这个字的意思有:①俸禄②官员等级③有条理④十年。在这里应该是第二个意思的引申,等级。
我个人的理解,按秩合并有两种:一个是根据树的高度,将更深的树的祖先作为另外一个的父亲,或者是根据节点的数量,将更多节点的树的祖先作为另外一个的父亲,当然前一种会好一点,但我个人比较喜欢后一种,这里也就给出后一种的代码,注意这里有个新的数组num,定义num[i]当i为祖先时表示整棵树的节点数量,否则没有意义(因为i不是祖先时也用不上),num数组在某些题目里也用的到。
procedure union(p,q:longint); var x,y:longint; begin x:=gf(p); y:=gf(q); if x=y then exit; if num[x]>=num[y] then begin f[y]:=x; num[x]:=num[x]+num[y]; end else begin f[x]:=y; num[y]:=num[x]+num[y]; end; end;
那么我个人对并查集的理解也就只有这些,希望能有神犇指点改正。
发表回复