无锡中小企业网站建设,python 自动 wordpress,贵阳官方网站,网络营销的概念和内涵带权并查集是在并查集的基础上加入数组来记录某些值#xff0c;比如说当前家族的人数 原理也较简单#xff0c;直接在合并时相加赋值就可以了#xff0c;但是不要忘记初始化
例题一.合并家族
给定一个数n#xff0c;代表总人数#xff0c;一开始每个人自己是一家#x…带权并查集是在并查集的基础上加入数组来记录某些值比如说当前家族的人数 原理也较简单直接在合并时相加赋值就可以了但是不要忘记初始化
例题一.合并家族
给定一个数n代表总人数一开始每个人自己是一家给定另一个数m代表操作总次数每次操作可以有三种方式
1、输入“C”和两个数代表把这两个数合并到一个家族中 2、输入“Q1”和两个数代表询问这两个数是否在同一家族中 3、输入“Q2”和一个数代表询问这个数所在的家族的总人数
这个题需要在普通并查集的基础上加入一个数组 d i s i dis_i disi 来记录家族的人的个数初始化时需要把每一个家族的人数归一合并时家族的人数也要相加赋值
#includebits/stdc.h
using namespace std;
int fa[100005],dis[100005],n,m;
int Find(int x){if(fa[x]x){return x;}int xxFind(fa[x]);return fa[x]xx;
}
void Union(int x,int y){xFind(x);yFind(y);if(x!y){fa[x]y;dis[y]dis[x];}
}
void Init(){for(int i1;in;i){dis[i]1;fa[i]i;}
}
int main(){scanf(%d%d,n,m);Init();for(int i1;im;i){char s[5];scanf(%s,s);if(s[0]C){int xx,yy;scanf(%d%d,xx,yy);Union(xx,yy);}else if(s[1]1){int xx,yy;scanf(%d%d,xx,yy);if(Find(xx)Find(yy)){printf(Yes\n);}else{printf(No\n);}}else{int xx;scanf(%d,xx);printf(%d\n,dis[Find(xx)]);}}return 0;
}例题二.信息传递
P2661 [NOIP2015 提高组] 信息传递 给定n个同学每个同学都会告诉一个同学自己的信息问进行几轮传递后这位同学能够收到自己的信息
每次传递都会耗费一轮所以这里的dis是用来存储耗费的轮数初始化为0每次合并时把轮数加一直到出现需合并的两数的祖先是同一人这就说明出现环了比较记录最小值
#includebits/stdc.h
using namespace std;
int fa[1000005],dis[1000005],minn,n,t;int Find(int x){if(fa[x]x){return x;}int rootFind(fa[x]);dis[x]dis[fa[x]];return fa[x]root;
}
void Union(int x,int y){int xxFind(x);int yyFind(y);if(xxyy){minnmin(minn,dis[x]dis[y]1);return ;}fa[xx]yy;dis[x]dis[y]1;
}
void Init(){for(int i0;in;i){fa[i]i;dis[i]0; }
}
int main(){scanf(%d,n);Init();minn0x3f3f3f3f;for(int i1;in;i){scanf(%d,t);Union(i,t);}printf(%d,minn);return 0;
}例题三.堆箱子
给定n和m分别代表箱子的总个数和操作的次数
每次操作有两种 1、输入“M”和两个数代表把第一个数所在的那一堆箱子放到第二个数所在的那堆箱子的上面 2、输入“C”和一个数代表询问那个数所代表的那个箱子的下面有多少个箱子
这道题不仅需要点权还需要边权点权记录箱子的个数边权记录该箱子之下箱子的个数在合并的过程中将边权赋值给点权边权相加
边权初始化为1点权初始化为0
#includebits/stdc.h
using namespace std;
int fa[1000005],dis[1000005],num[1000005],n,m;
int Find(int x){if(fa[x]x){return x;}int rootFind(fa[x]);dis[x]dis[fa[x]];return fa[x]root;
}
void Union(int x,int y){int xxFind(x);int yyFind(y);if(xxyy){return ;}dis[xx]num[yy];num[yy]num[xx];fa[xx]yy;
}
void Init(){for(int i0;in;i){fa[i]i;num[i]1;dis[i]0; }
}
int main(){scanf(%d%d,n,m);Init();for(int i1;im;i){char s[5];scanf(%s,s);if(s[0]M){int x1,y1;scanf(%d%d,x1,y1);Union(x1,y1);}else{int x1;scanf(%d,x1);int y1Find(x1);printf(%d\n,dis[x1]);}}return 0;
}种类并查集
种类并查集可以维护对立的关系例如敌人的敌人是朋友
例题四.食物链
P2024 [NOI2001] 食物链
输入nk分别代表动物的总个数和话的个数 每句话有两种形式 1、输入“1”和两个数代表这两个数是同类 2、输入“2”和两个数代表第一个动物吃第二个动物
要求判断给定的话里面有多少是假话
假话有那么几种情况1、数字比n大 2、违背了之前所说的关系 3、自己吃自己
此题需要开一个3倍大小的 f a fa fa 一倍下标存本身二倍下标存猎物三倍下标存天敌 输入1时二者本身、二者猎物、二者天敌都是同类把他们合并起来 输入2时X是Y的天敌所以Y的天敌和X是同类把X和2nY合并起来X的猎物也应该和Y是同类所以把Xn和Y合并起来还有题目中强调的“食物链呈环形A吃BB吃CC吃A”所以X的天敌应是Y的猎物把X2n和Yn合并在一块
每次操作前应该判断是否合规如果不合规anscontinue不正确的情况不操作
#includebits/stdc.h
using namespace std;
int fa[300005],n,m,ans;
int Find(int x){if(fa[x]x){return x;}return fa[x]Find(fa[x]);
}
void Union(int x,int y){int xxFind(x);int yyFind(y);if(xxyy){return ;}fa[xx]yy;
}
void Init(){for(int i1;i3*n;i){fa[i]i;}
}
int main(){scanf(%d%d,n,m);Init();for(int i1;im;i){int tt;scanf(%d,tt);int xx,yy;scanf(%d%d,xx,yy);if(tt1){if(xxn||yyn||Find(xxn)Find(yy)||Find(xx2*n)Find(yy)){ans;continue;}Union(xx,yy);Union(xxn,yyn);Union(xx2*n,yy2*n);}else{if(Find(xx)Find(yy)||Find(xx2*n)Find(yy)||xxyy||xxn||yyn){ans;continue;}Union(xx,yy2*n);Union(xxn,yy);Union(xx2*n,yyn);}}printf(%d\n,ans);return 0;
}
