浅谈并查集&种类并查集&带权并查集

时间:2022-06-08 10:05:37

并查集&种类并查集&带权并查集

前言:

因为是学习记录,所以知识讲解+例题推荐+练习题解都是放在一起的qvq


目录

  • 并查集基础知识

  • 并查集基础题目

  • 种类并查集知识

  • 种类并查集题目

  • 并查集&种类并查集部分题解

  • 带权并查集知识

  • 带权并查集题目

  • 带权并查集题解


并查集基础:

普通的并查集+路径压缩相信大家还是会的,就主要是两个操作:

  1. 查询某个元素属于哪个集合

  2. 合并两个集合成为一个大集合

提出一点,就是求最小生成树的Kruskal算法也是在使用并查集后才是完整的Kruskal

并查集基础题目:

通过“程序自动分析”这道题,我们能够看到,并查集能在一张无向图中维护节点之间的连通性,这是它的基本用途之一

实际上,并查集擅长动态维护许多具有传递性的关系,如这道题中:“等于”就是一种传递关系,但是“不等于”显然不具有传递性

但在某些问题中,“传递关系”不止一种,并且这些“传递关系”能够互相导出,此时可以使用以下的扩展域或者边带权的并查集来解决


种类并查集:

  • 写在前面

如果你在洛谷或其他OJ上独立做过了几道并查集的题,那么可以接触升级版的并查集了:带权并查集、种类并查集

  • 知识搬运
  1. 种类并查集:即在普通并查集“亲戚的亲戚也是亲戚”的基础上再进行一些“分类”,但是这个分类呢并不是根据物品的种类来进行分类,而是类似“敌人的敌人是朋友”的分类(并没有说明“朋友的敌人是我的敌人”!要根据具体题目分析

  2. 种类并查集常规套路:不是开多个或多维并查集数组,而是扩大并查集规模

举个栗子:我们要维护朋友和敌人这两个关系,则将普通并查集的规模扩大两倍,原来的1~n还是存放朋友关系,但是n+1~2n则是存放敌人关系,然后每次操作都分别维护

  1. 种类并查集加强版:上面举的例子是针对两种对立关系,但是有些题目会涉及三种循环关系,怎么做呢?其实就是将扩大两倍规模变为扩大三倍规模(下面有例题会讲到)

种类并查集题目:


并查集&种类并查集题解:

题目请大家直接点开看,因为描述很清晰就不再赘述了,直接来讲思路(这题就是思维难度大,容易绕晕QAQ)

  1. 判断是否是假话,其实就是判断当前给出的条件是否与之前构建的并查集关系树冲突,冲突则是假话(于是转换了题目后,就变成维护种类并查集

  2. 我们需要维护三种关系:“同类”、“猎物”、“天敌”,所以扩大三倍规模,第一倍维护同类、第二倍维护猎物、第三倍维护天敌

  3. 搞清楚三种关系的传递:猎物的猎物是天敌、天敌的猎物是同类、同类的猎物是猎物、同类的天敌是天敌(反正就是A吃B,B吃C,C吃B

  4. 判断是假话的三条规则:①当前给出x、y是同类,但前面已经构建x、y是天敌关系,是假话;②当前给出x是y的天敌,但前面已经构建x、y是同类或y是x的天敌,是假话;③x、y的编号超出了食物链的最大编号(简单明了)

好了,思路如上,我们可以开始敲代码了quq:

#include <bits/stdc++.h>
using namespace std;
int n,k,u,v,op,ans,fa[150010]; inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
} int main() {
scanf("%d%d",&n,&k);
for(register int i=1;i<=3*n;i++) fa[i]=i; //扩大三倍规模
for(register int i=1;i<=k;i++) {
scanf("%d%d%d",&op,&u,&v);
if(u>n||v>n) { //不存在于食物链中,假话
ans++;
continue;
}
if(op==1) { //如果两者是同类
if(find(u)==find(v+n)||find(u+n)==find(v)) { //如果两者已经是天敌关系,假话
ans++;
continue;
}
fa[find(u)]=find(v); //合并
fa[find(u+n)]=find(v+n);
fa[find(u+n+n)]=find(v+n+n);
}
else { //如果x是y天敌
if(find(u)==find(v)||find(u)==find(v+n)) { //如果两者已经是同类或y是x天敌,假话
ans++;
continue;
}
fa[find(u)]=find(v+n+n); //注意一下对应关系!
fa[find(u+n)]=find(v);
fa[find(u+n+n)]=find(v+n);
}
}
printf("%d",ans);
return 0;
}

题目简述一下:给定n个罪犯,m个关系;对于每个关系给出两个罪犯在同一所*中的怨气值;要求将所有罪犯分到两所*,要让这两所*中所有怨气值的最大值最小

现在来讲思路:

  1. 首先我们可以想到贪心,怎么贪?即将所有怨气值从大到小排序,然后首先将怨气值大的分开,直到不能这么干

  2. 但我们始终需要维护两所*中的怨气值,所以我们不妨将种类并查集作为解题主体再加上排序作为辅助

  3. 怎么种类并查集?首先还是先排序,如果当前罪犯x的敌人为空,则将当前关系对应的罪犯y设为x的敌人;之后再遇到罪犯x与其他罪犯z有怨气关系时,就将罪犯z与罪犯y建立朋友关系(“敌人的敌人是朋友”的思想)

  4. 你可能会疑惑,罪犯y和罪犯z也有可能是互相的敌人啊,怎么就构建朋友关系了呢?可如果全部处理成敌人关系我们将无法解决这道题,但是转换一下思路,我们已经将怨气值从大到小排序,所以怨气值大的看做敌人,之后再遇到敌人就将两个敌人合并为朋友

  5. 这并不与在m个关系的描述中罪犯y与罪犯z是敌人相冲突,因为y与z的怨气值小于x与y的怨气值,不会妨碍我们最终求得怨气值的最大值最小

  6. 如果在处理过程中找到了一组罪犯u和罪犯v,满足两人在同一集合中,就直接输出u和v的怨气值

  7. 如果处理完所有关系都没有输出,则输出0(题目要求的,因为忘了写,白白WA了一个点)

感觉讲得有点绕QAQ,大家在草稿本上手模一下样例应该就懂了,下面给出代码:

#include <bits/stdc++.h>
using namespace std;
int n,m,fa[400010]; struct node {
int u,v,w;
} a[400010]; inline bool cmp(node x,node y) {
return x.w>y.w;
} inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
} int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=2*n;i++) fa[i]=i; //扩大两倍规模:一倍存朋友,二倍存敌人
for(register int i=1;i<=m;i++) {
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
}
sort(a+1,a+1+m,cmp); //怨气值从大到小排序
for(register int i=1;i<=m;i++) {
if(find(a[i].u)==find(a[i].v)) { //找到了最大值最小的怨气值
printf("%d",a[i].w);
return 0;
}
if(find(a[i].u+n)==a[i].u) { //如果还没有敌人,将当前关系对应的罪犯标记为敌人
fa[a[i].u+n]=a[i].v;
}
else if(find(a[i].u+n)!=a[i].u) { //如果有敌人了,则将之前的敌人与现在的敌人合并为朋友
fa[find(a[i].u+n)]=find(a[i].v);
}
if(find(a[i].v+n)==a[i].v) { //双向的
fa[a[i].v+n]=a[i].u;
}
else if(find(a[i].v+n)!=a[i].v) {
fa[find(a[i].v+n)]=find(a[i].u);
}
}
puts("0"); //没有找到,输出0
return 0;
}

说在前面:

这道题因为蒟蒻只会map实现离散化,但是这道题第二个点还是会T,只有90pts(吸氧倒是能A掉)所以各位dalao可以跳过这道题的题解,以下讲的是90pts 的做法,抱歉啊!(咕咕咕)

更新于2020.6.18 蒟蒻下午去学习了一下离散化及其实现,写了学习记录

题目请大家直接点击题目链接查看,不多赘述,直接讲思路

  1. 这题就是普通的并查集,但是数据太大了,直接存放肯定炸得体无完肤,所以我们需要引入“离散化”来存放数据

  2. 离散化大致有两种:

(1)去重(可以用到unique去重函数)+ 排序 +二分索引(可以用到lower_bound函数)

(2)Hash表(散列表):如果维护的好,可以实现O(1)的查询

下面给出蒟蒻的90pts代码满分代码(更新啦~使用STL实现离散化,具体可见上面的“学习记录”):

#include <bits/stdc++.h>
using namespace std;
bool flag;
int t,n,tot,res,fa[2000010],b[6000010]; struct node {
int u,v,e;
} a[2000010]; inline bool cmp(node x,node y) {
return x.e>y.e;
} inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
} int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
tot=0;
memset(a,0,sizeof(a)); //记得清空啊
memset(b,0,sizeof(b));
memset(fa,0,sizeof(fa));
for(register int i=1;i<=n;i++) {
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].e);
b[++tot]=a[i].u;
b[++tot]=a[i].v;
}
sort(b+1,b+1+tot); //第一步,排序
res=unique(b+1,b+1+tot)-(b+1); //第二步,去重
for(register int i=1;i<=n;i++) { //第三步,二分索引
a[i].u=lower_bound(b+1,b+res+1,a[i].u)-b;
a[i].v=lower_bound(b+1,b+res+1,a[i].v)-b;
}
for(register int i=1;i<=res;i++) fa[i]=i;
sort(a+1,a+1+n,cmp); //先处理所有合并的情况
flag=true;
for(register int i=1;i<=n;i++) {
if(a[i].e==1) {
fa[find(a[i].u)]=find(a[i].v);
}
else {
if(find(a[i].u)==find(a[i].v)) {
puts("NO");
flag=false; //打上标记
break;
}
}
}
if(flag==true) puts("YES");
}
return 0;
}

洛谷P6121 [USACO16OPEN]Closing the Farm G (此为加强版)

直接讲加强版的思路(其实都差不多啦):

  1. 题目要求按顺序关闭谷仓,每次关闭都要判断当前剩余所有谷仓是否联通

  2. 我们转换一下,将顺序关闭改为倒序开启!,每一次开启就相当于插入一个点,然后用并查集维护联通块

  3. 但是跟其他并查集不一样,我们的fa数组不能直接初始化,而是应该开u号仓就将fa[u]赋成u,联通块++

  4. 对于现在开的u号仓,我们遍历与u号仓有路径相连的其他仓库,进行判断

  5. 判断:如果遍历到的v号仓库还没有开仓(即fa[v]=0)则跳过不管

  6. 如果已经开过仓了,再判断i和v是否在一个集合,如果不在就将u、v合并再将联通块--

  7. 处理完所有与u相连的仓库后,将当前的联通块个数保存在ans[u]中,最后循环判断如果ans[i]==1就输出YES,反之输出NO

下面给出加强版代码(终于没有咕咕咕了,更新于2020.6.18):

#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,tot,sum,fa[2000010],ans[2000010],head[2000010],order[2000010]; //开大一点 struct node {
int to,net;
} a[2000010]; inline void add(int x,int y) { //链式前向星存边
a[++tot].to=y;
a[tot].net=head[x];
head[x]=tot;
} inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
} int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
scanf("%d%d",&u,&v);
add(u,v); //双向边
add(v,u);
}
for(register int i=1;i<=n;i++) {
scanf("%d",&order[i]);
}
for(register int i=n;i>=1;i--) { //倒叙开仓
sum++; //联通块个数
fa[order[i]]=order[i];
for(register int j=head[order[i]];j;j=a[j].net) { //遍历与order[i]相连的v仓库
int v=a[j].to;
if(fa[find(v)]!=0) { //v号仓库已经开过
if(find(v)!=find(order[i])) { //不在一个集合就合并,联通块--
sum--;
fa[find(v)]=find(order[i]);
}
}
}
ans[i]=sum;
}
for(register int i=1;i<=n;i++) { //判断输出
if(ans[i]==1) puts("YES");
else puts("NO");
}
return 0;
}

带权并查集:

  • 写在前面

关于这个带权并查集,蒟蒻做了两道题,但貌似树的形态都是链,所以和同学还在讨论其他情况需不需要维护size数组(size数组在下面会讲)和一些其他问题

所以现在只讲解链的情况,请见谅(有dalao给讲讲嘛?)

  • 知识搬运

并查集实际上是由若干棵树构成的森林,我们可以在树中的每条边上记录一个权值,即维护一个数组d,用d[i]保存节点i到父节点fa[i]之间的边权

在每次路径压缩后,每个访问过的节点都会直接指向树根,如果我们同时更新这些节点的d值,就可以利用路径压缩过程来统计每个节点到树根之间的路径信息

题型一般就是给出点之间的合并,然后询问两个点之间的距离

下面给出在路径压缩时维护d值的代码(注意一下写法哦!建议照下面这样规范敲代码quq):

inline int find(int x) {
if(fa[x]==x) return x;
int root=find(fa[x]); //注意一下写法,先将find(fa[x])存放在root中,否则会出错
d[x]+=d[fa[x]];
return fa[x]=root;
}

带权并查集题目:

再次温馨提示:以下例题都是链的情况(应该是维护点权)


带权并查集题解:

题目转换思路:

一共有30000列,每列一艘战舰(摆明了是链的形态)

给定T组对于u、v进行合并或查询,合并时将u这一列移动到v这一列后面;查询时输出u和v之间的战舰数(所以战舰数就是权值)

所以我们开三个数组,一个fa[i]表示i的父亲节点,一个d[i]表示i到其父节点的边权,一个size[i]表示i所在子树的大小

下面给出代码:

#include  <bits/stdc++.h>
using namespace std;
char op;
int T,u,v,d[30010],fa[30010],size[30010]; inline int find(int x) {
if(fa[x]==x) return x;
int root=find(fa[x]); //注意一下写法,先将find(fa[x])存放在root中,否则会出错
d[x]+=d[fa[x]];
return fa[x]=root;
} int main () {
scanf("%d",&T);
for(register int i=1;i<=30001;i++) {
fa[i]=i;
size[i]=1; //每棵子树的大小初始都为1
}
for(register int i=1;i<=T;i++) {
cin>>op;
scanf("%d%d",&u,&v);
if(op=='M') {
int uu=find(u);
int vv=find(v);
fa[uu]=vv; //把u这棵树全部搬到v这棵树下面,成为v这棵树的子树
d[uu]+=size[vv]; //更新u这棵子树的祖先到v这棵树的距离
size[vv]+=size[uu]; //更新v这棵树的大小
}
else {
if(find(u)!=find(v)) puts("-1");
else printf("%d\n",abs(d[u]-d[v])-1);
} }
return 0;
}

这道题跟“银河英雄传说”几乎一模一样,就是合并和查询的方式有点差别,现在来讲思路转换:

合并时给出u、v,要将u移到v上面(转换一下,就是将v移到u下面!这就跟“银河英雄传说”一样了啊)

查询时只给出z,要求输出z之下的积木数(积木数=战舰数=权值)

代码如下:

#include  <bits/stdc++.h>
using namespace std;
char op;
int T,u,v,d[30010],fa[30010],size[30010]; inline int find(int x) {
if(fa[x]==x) return x;
int root=find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
} int main () {
scanf("%d",&T);
for(register int i=1;i<=30000;i++) {
fa[i]=i;
size[i]=1;
}
for(register int i=1;i<=T;i++) {
cin>>op;
if(op=='M') {
scanf("%d%d",&u,&v);
int uu=find(u);
int vv=find(v);
fa[vv]=uu; //注意一下这里与“银河英雄传说”合并的区别
d[vv]+=size[uu];
size[uu]+=size[vv];
}
else {
scanf("%d",&u);
printf("%d\n",size[find(u)]-d[u]-1); //注意是u的根节点的size-d[u],不能直接写成u的size-d[u]
} }
return 0;
}

带权并查集的一点讨论:

讨论:什么时候需要维护size数组和dis数组

现在给出一个不维护size数组的小程序,处理的是边权(就直接维护dis),上面的例题是点权(都要维护)

#include<bits/stdc++.h>
using namespace std;
int fa[30010],dis[30010];
inline int find(int x) {
if(x==a[x]) return x;
int root=find(fa[x]);
dis[x]+=dis[fa[x]];
return fa[x]=root;
} inline void un(int x,int y) {
int xx=find(x),yy=find(y);
if(xx==yy) return;
dis[xx]+=dis[y]+1; //这里的1指的是xx到y的边权值
fa[xx]=yy;
} int x,y; int main() {
for(register int i=1;i<=100;i++) fa[i]=i;
while(cin>>x>>y) {
un(x,y);
for(register int i=1;i<=5;i++) find(i); //每合并一次就要全部更新i到根节点的距离
for(register int i=1;i<=5;i++) cout<<dis[i]<<" "; //输出i到根节点的距离
cout<<endl;
}
return 0;
}

后序:

如果大家的理解和以上我的理解有任何出入,欢迎大家留言,我们一起讨论啊!

To be continue....