并查集这篇讲解并查集及拓展 主要放在并查集进阶内容上目录并查集经典并查集find的路径压缩带权并查集扩展域并查集总结经典并查集并查集用于维护不相交集合的合并与查询共有两个操作:f i n d ( x ) find(x)find(x)返回x xx所在集合的代表元(根/老大)m e r g e ( x , y ) merge(x, y)merge(x,y)将x , y x, yx,y所在集合合并用数组f a [ i ] fa[i]fa[i]表示i ii的父亲节点 一个集合的代表元的父亲是它自己初始化f a [ i ] i fa[i]ifa[i]i简洁模板如下intfa[MAXN];intfind(intx){if(fa[x]x)returnx;// 若父亲为自己 则找到了该集合的代表元returnfa[x]find(fa[x]);// 路径压缩}voidmerge(intx,inty){fa[find(x)]find(y);// 将x集合代表元的父亲指向y集合代表元}find的路径压缩也就是我们在上面看到的f a [ x ] f i n d ( f a [ x ] ) fa[x]find(fa[x])fa[x]find(fa[x])目的是为了把x xx的父亲自动指向当前集合的代表元 最终路径压缩的结果就是:带权并查集经典并查集仅能判断两元素是否在同一集合 而带权并查集解决了元素之间的相对关系 比如:与根节点的距离与父节点的差值等等相对关系核心思想每个节点除了f a [ x ] fa[x]fa[x]以外 再来一个v a l [ x ] val[x]val[x]表示节点x xx到其父节点f a [ x ] fa[x]fa[x]的某种关系故在路径压缩时 需要将v a l [ x ] val[x]val[x]更新为x xx到根节点的关系在合并操作中 需要计算出两根关系code我们以维护节点到根的距离为例 设一个d [ x ] d[x]d[x]为x xx到父节点f a [ x ] fa[x]fa[x]的距离find操作:intfind(intx){if(fa[x]x)returnx;introotfind(fa[x]);// 先递归得根// 更新x到根的距离 x到原父节点距离父节点到爷爷节点(压缩后即为根节点)的距离d[x]d[fa[x]];returnfa[x]root;//路径压缩merge操作://将x集合同y集合合并 且x到y的距离为wvoidmerge(intx,inty,intw){intrxfind(x),ryfind(y);// 找根节点if(rxry)return;fa[rx]ry;// 这里将x集合合并到y集合// x到ry x到rx rx到ry d[x]d[rx]// y到ry d[y]// 而x到y是w 所以d[x]d[rx]-d[y] wd[rx]wd[y]-d[x]}例题:P1196 银河英雄传说题意:n nn个队列 两种操作:将i ii所在队列接到j jj的尾部查询i , j i,ji,j是否同一队列 输出间隔节点数解法:维护d [ x ] d[x]d[x]为x xx到队列头节点的距离,s z [ x ] sz[x]sz[x]为以x xx为根的集合大小 用于更新距离#includebits/stdc.husingnamespacestd;#definerdread()#defineintlonglong#defineputc(a)putchar(a)#defineenterputchar(\n)#definefo(a,b,c)for(intab;ac;a)constintN3e47,INF0x3f3f3f3f3f3f3f3f;intread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}returnx*f;}intT,n3e44;intf[N],sz[N];intd[N];intfind(intx){if(f[x]x)returnx;introotfind(f[x]);d[x]d[f[x]];returnf[x]root;}// 将x合并到yvoidmerge(intx,inty){intxxfind(x),yyfind(y);f[xx]yy;//将x合并到yd[xx]sz[yy];//xx到yy的距离 就是原来yy队列的长度sz[yy]sz[xx];// yy队列加上了xx队列长度}intres(intx,inty){intxxfind(x),yyfind(y);if(xx!yy)return-1;returnabs(d[x]-d[y])-1;}signedmain(){Trd;fo(i,1,n)sz[i]1,d[i]0,f[i]i;while(T--){charop;intx,y;scanf( %c,op);xrd;yrd;if(opM){merge(x,y);}else{intansres(x,y);printf(%lld\n,ans);}}return0;}扩展域并查集扩展并查集用于处理多种对立关系例如:食物链 (A吃B B吃C C吃A)敌人的敌人是朋友 (敌人朋友关系)它不需要权值的计算 而是把每个元素分成很多个域用其连通关系表示约束 然后维护每个域的连通性 这么讲很难懂 讲个题例题:P2024 [NOI2001] 食物链我们把并查集分为三个域:x xx同类域:x xxx xx吃域:x n xnxnx xx被吃域:x 2 ∗ n x2*nx2∗n然后我们来根据题目操作维护它们的关系 详见代码:#includebits/stdc.husingnamespacestd;#definerdread()#defineintlonglong#defineputc(a)putchar(a)#defineenterputchar(\n)#definefo(a,b,c)for(intab;ac;a)constintN1e64,INF0x3f3f3f3f3f3f3f3f;intread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}returnx*f;}intn,k;intf[3*N],sz[3*N];/* 1~n 同类 n1~2n 吃域 2n1~3n 被吃域 *///常规find和merge操作intfind(intx){//find简写returnf[x]x?x:f[x]find(f[x]);}voidmerge(intx,inty){xfind(x);yfind(y);if(xy)return;// 启发式合并 小集合合并到大集合 可以不管if(sz[x]sz[y])swap(x,y);f[x]y;// 将x合并到ysz[y]sz[x];}signedmain(){nrd;krd;// 初始化fo(i,1,n*3)f[i]i,sz[i]1;intans0;//假话个数fo(i,1,k){intop,x,y;oprd;xrd;yrd;if(xn||yn){ans;continue;}if(op1){// xy是同类//y域不能在x的吃域中 x域不能在y的吃域中if(find(xn)find(y)||find(yn)find(x)){ans;continue;}//由于它们是同类 故各个域都连通merge(x,y);merge(xn,yn);merge(x2*n,y2*n);}else{//x吃y//xy不能为同类 x域不能在y的吃域if(find(x)find(y)||xy||find(yn)find(x)){ans;continue;}merge(xn,y);//x吃域加上y域merge(x,y2*n);//y被吃域加上x域merge(x2*n,yn);//x被吃域加上y吃域 (根据食物链题意)}}printf(%lld,ans);return0;}总结带权并查集扩展域并查集实现推导权值更新公式直接合并适用场景数值关系等关系种类固定灵活性可维护距离差值等处理对立关系