集训队讲座第十讲并查集的深化与扩展.ppt

集训队讲座--第十讲并查集的深化与扩展(Merge_Find_Set)Index~1:并查集的概念。2:并查集的优化。3:并查集的扩展。4:并查集的应用:LCATarjan算法。5:区间最优值RMQ算法。概念与实现方式概念:并查集——不相交集合每棵树一个集合,根为集合标识。树的形态并不重要,重要的是有哪些节点实现方式:一维数组的“森林表示法”。几个定义:祖先,父亲,子孙~生活中的集合~并查集的基本操作MakeSet(x):建立一个新集合x。x应该不在现有的任何一个集合中出现。Find(S,x):返回x所在集合的代表元素。Merge(x,y):把x所在的集合和y所在的集合合并。不可忽视的弊端:无法高效的找寻儿子节点!!!并查集的优化1:启发式并查集:让深度较小的树成为深度较大的树的子树~2:路径压缩:找到最久远的祖先时“顺便”把它的子孙直接连接到它上面~启发式并查集1564维护一个dep[]数组记入元素代表的有向树的深度。每次合并操作将深度较小的集合合并到深度较大的集合中,并维护dep数组。237Dep[1]==2dep[4]==3启发式并查集boolMerge(intx,inty){ x=find(x); y=find(y); if(x!=y)returnfalse; if(dep[x]<dep[y])tree[x]=y; elseif(dep[x]>dep[y])tree[y]=x; elsetree[x]=y,dep[y]++; returntrue;}路径压缩49611110812202116612182**********路径压缩的实现递归式:intfind(intx){ if(tree[x]==-1) returnx; returntree[x]=find(tree[x]);}