优秀的网站建设策划书,网站建设的必要性及意义,平面设计在哪里接单,网页制作与设计在工作中的应用作者#xff1a;指针不指南吗 专栏#xff1a;Acwing 蓝桥集训每日一题 #x1f43e;或许会很慢#xff0c;但是不可以停下来#x1f43e; 文章目录1.亲戚2.合并集合3.连通块中点的数量有关并查集的知识学习可以移步至——
【算法】——并查集1.亲戚 或许你并不知道#… 作者指针不指南吗 专栏Acwing 蓝桥集训每日一题 或许会很慢但是不可以停下来 文章目录1.亲戚2.合并集合3.连通块中点的数量有关并查集的知识学习可以移步至——
【算法】——并查集1.亲戚 或许你并不知道你的某个朋友是你的亲戚。 他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。 如果能得到完整的家谱判断两个人是否是亲戚应该是可行的但如果两个人的最近公共祖先与他们相隔好几代使得家谱十分庞大那么检验亲戚关系实非人力所能及。 在这种情况下最好的帮手就是计算机。 为了将问题简化你将得到一些亲戚关系的信息如Marry和Tom是亲戚Tom和Ben是亲戚等等。 从这些信息中你可以推出Marry和Ben是亲戚。 请写一个程序对于我们的关于亲戚关系的提问以最快的速度给出答案。 输入格式 输入由两部分组成。 第一部分以 N,M开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行每行有两个数 ai,bia_i,b_iai,bi 表示已知 aia_iai 和 bib_ibi 是亲戚。 第二部分以 Q 开始。以下 Q 行有 Q 个询问每行为 ci,dic_i,d_ici,di 表示询问 cic_ici 和 did_idi 是否为亲戚。 输出格式 对于每个询问ci,dic_i,d_ici,di 输出一行若 cic_ici 和 did_idi 为亲戚则输出“Yes”否则输出“No”。 数据范围 1≤N≤20000, 1≤M≤10610^6106 , 1≤Q≤10610^6106 . 输入样例 10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9输出样例 Yes
No
Yes思路 把每个家族看成一个集合人之间互为亲戚则说明他们是一个家族的用一个编号来表示这个题比较简单就是并查集的两个朴素操作 两个人互为亲戚进行家族合并即并查集合并查询两个人是否为亲戚即看看这两人的家族是否一样 代码实现 #includebits/stdc.h
using namespace std;const int N200010;int n,m; //n表示人数m表示操作的次数
int p[N];int find(int x) //找到家族编号即根节点
{if(p[x]!x) p[x]find(p[x]);return p[x];
}int main()
{scanf(%d%d,n,m);for(int i1;in;i) p[i]i; //初始化父节点while(m--){ //m次合并操作亲戚互认int a,b;scanf(%d%d,a,b);if(find(a)!find(b)) p[find(a)]find(b); //家族集合合并}int q;cinq;while(q--){ //q次查询是否是亲戚一个家族集合的int x,y;scanf(%d%d,x,y);if(find(x)find(y)) puts(Yes); else puts(No);}return 0;
}2.合并集合 一共有 n 个数编号是 1∼n最开始每个数各自在一个集合中。 现在要进行 m 个操作操作共有两种 M a b将编号为 a 和 b 的两个数所在的集合合并如果两个数已经在同一个集合中则忽略这个操作Q a b询问编号为 a 和 b 的两个数是否在同一个集合中 输入格式 第一行输入整数 n 和 m。 接下来 m 行每行包含一个操作指令指令为 M a b 或 Q a b 中的一种。 输出格式 对于每个询问指令 Q a b都要输出一个结果如果 a 和 b 在同一集合内则输出 Yes否则输出 No。 每个结果占一行。 数据范围 1≤n,m≤10510^5105 输入样例 4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例 Yes
No
Yes代码实现 #includebits/stdc.h
using namespace std;const int N100010;int n,m; //n表示点的数量m表示操作的次数
int p[N]; //存的每个节点的父节点int find(int x) //返回x的祖宗节点路径压缩
{if(p[x]!x) p[x]find(p[x]);return p[x];
}int main()
{scanf(%d%d,n,m);for(int i1;in;i) p[i]i; //最开始每个点都各自在一个集合中so父节点就是他本身while(m--){char op[2];int a,b;scanf(%s%d %d,op,a,b);//合并if(op[0]M) p[find(a)]p[find(b)]; //让a的祖宗节点等于b的祖宗节点让a的祖宗节点直接插在b祖宗节点下面else{if(find(a)find(b)) puts(Yes); //判断是否属于同一个集合else puts(No);} }return 0;
}注意
读入字母M或者是Q的时候使用字符串op[2],是因为直接用char的话可能会出现空格换行的问题作物这种比较保险记得在后面使用的时候用op[0],不能直接使用op
puts自动包含换行
3.连通块中点的数量 给定一个包含 n 个点编号为 1∼n的无向图初始时图中没有边。 现在要进行 m 个操作操作共有三种 C a b在点 a 和点 b 之间连一条边a 和 b 可能相等Q1 a b询问点 a 和点 b 是否在同一个连通块中a 和 b 可能相等Q2 a询问点 a 所在连通块中点的数量 输入格式 第一行输入整数 n 和 m。 接下来 m 行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。 输出格式 对于每个询问指令 Q1 a b如果 a 和 b 在同一个连通块中则输出 Yes否则输出 No。 对于每个询问指令 Q2 a输出一个整数表示点 a 所在连通块中点的数量 每个结果占一行。 数据范围 1≤n,m≤10510^5105 输入样例 5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例 Yes
2
3思路 连通块就是一个点的集合集合中的点可以相互到达直接或者是间接都是可以的 这时候我们可以把它类比成一个树运用并查集一个点集合我们可以用一个编号来表示属于同一个编号就说明两个点之间可以相互到达在一个连通块里面 有三个操作 两点之间连一条边那么这两个点所在集合中的点都是可以相互到达的即合成一个连通块用并查集中的合并操作 判断是否在一个连通块用并查集的查询 询问一个点集合的数量需要我们额外维护初始化的时候每个集合1个合并的时候两个集合数量相加最后输出即可 代码实现 #includebits/stdc.husing namespace std;const int N1000010;
int n,m;
int p[N],sizel[N]; //p表示父节点sizel表示集合的大小记住sizel里面放的是祖宗节点后面容易出错int find(int n) //返回祖宗节点
{if(p[n]!n) p[n]find(p[n]);return p[n];
}int main()
{scanf(%d%d,n,m); //读入点的数量和操作的次数for(int i1;in;i){ //初始化父节点就是它本身集合大小都是1只有他自己p[i]i;sizel[i]1;}char op[5]; while(m--){scanf(%s,op); //读入操作的名字if(op[0]C){ //合并int a,b;scanf(%d%d,a,b);if(find(a)find(b)) continue; //相同则进入下个循环else{ //不同即操作两步的顺序不能反sizel[find(b)]sizel[find(a)]; //b的集合大小加上a的集合大小p[find(a)]find(b); //让a的祖宗节点指向b的祖宗节点}}else if(op[1]1){ //查询是否一个集合int a,b;scanf(%d%d,a,b);if(find(a)find(b)) puts(Yes);else puts(No);}else{if(op[1]2) { //输出集合大小int d;scanf(%d,d);printf(%d\n,sizel[find(d)]); }}}return 0;
} 文章转载自： http://www.morning.lbxhy.cn.gov.cn.lbxhy.cn http://www.morning.bnlkc.cn.gov.cn.bnlkc.cn http://www.morning.qwbls.cn.gov.cn.qwbls.cn http://www.morning.hrgxk.cn.gov.cn.hrgxk.cn http://www.morning.ggjlm.cn.gov.cn.ggjlm.cn http://www.morning.lflsq.cn.gov.cn.lflsq.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.llgpk.cn.gov.cn.llgpk.cn http://www.morning.bktzr.cn.gov.cn.bktzr.cn http://www.morning.rsbqq.cn.gov.cn.rsbqq.cn http://www.morning.rnyhx.cn.gov.cn.rnyhx.cn http://www.morning.rhpgk.cn.gov.cn.rhpgk.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.mxdiy.com.gov.cn.mxdiy.com http://www.morning.rgfx.cn.gov.cn.rgfx.cn http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.zxfr.cn.gov.cn.zxfr.cn http://www.morning.phlrp.cn.gov.cn.phlrp.cn http://www.morning.tssmk.cn.gov.cn.tssmk.cn http://www.morning.jxdhc.cn.gov.cn.jxdhc.cn http://www.morning.rbzd.cn.gov.cn.rbzd.cn http://www.morning.rhsg.cn.gov.cn.rhsg.cn http://www.morning.gpnwq.cn.gov.cn.gpnwq.cn http://www.morning.kdlzz.cn.gov.cn.kdlzz.cn http://www.morning.hnzrl.cn.gov.cn.hnzrl.cn http://www.morning.hbxnb.cn.gov.cn.hbxnb.cn http://www.morning.ljfjm.cn.gov.cn.ljfjm.cn http://www.morning.dtmjn.cn.gov.cn.dtmjn.cn http://www.morning.rkzk.cn.gov.cn.rkzk.cn http://www.morning.qmfhh.cn.gov.cn.qmfhh.cn http://www.morning.zkgpg.cn.gov.cn.zkgpg.cn http://www.morning.dbnrl.cn.gov.cn.dbnrl.cn http://www.morning.qfwfj.cn.gov.cn.qfwfj.cn http://www.morning.rbqlw.cn.gov.cn.rbqlw.cn http://www.morning.mlnbd.cn.gov.cn.mlnbd.cn http://www.morning.rybr.cn.gov.cn.rybr.cn http://www.morning.snmth.cn.gov.cn.snmth.cn http://www.morning.pbsfq.cn.gov.cn.pbsfq.cn http://www.morning.hytr.cn.gov.cn.hytr.cn http://www.morning.dmnqh.cn.gov.cn.dmnqh.cn http://www.morning.sthgm.cn.gov.cn.sthgm.cn http://www.morning.bsxws.cn.gov.cn.bsxws.cn http://www.morning.zyslyq.cn.gov.cn.zyslyq.cn http://www.morning.jjzrh.cn.gov.cn.jjzrh.cn http://www.morning.zylrk.cn.gov.cn.zylrk.cn http://www.morning.qbfwb.cn.gov.cn.qbfwb.cn http://www.morning.tbhlc.cn.gov.cn.tbhlc.cn http://www.morning.ey3h2d.cn.gov.cn.ey3h2d.cn http://www.morning.dbrpl.cn.gov.cn.dbrpl.cn http://www.morning.dztp.cn.gov.cn.dztp.cn http://www.morning.rcmcw.cn.gov.cn.rcmcw.cn http://www.morning.mzydm.cn.gov.cn.mzydm.cn http://www.morning.wqbfd.cn.gov.cn.wqbfd.cn http://www.morning.jcffp.cn.gov.cn.jcffp.cn http://www.morning.rkgyx.cn.gov.cn.rkgyx.cn http://www.morning.fbmrz.cn.gov.cn.fbmrz.cn http://www.morning.ssfq.cn.gov.cn.ssfq.cn http://www.morning.mgbsp.cn.gov.cn.mgbsp.cn http://www.morning.wqgr.cn.gov.cn.wqgr.cn http://www.morning.bftqc.cn.gov.cn.bftqc.cn http://www.morning.rmtmk.cn.gov.cn.rmtmk.cn http://www.morning.txzqf.cn.gov.cn.txzqf.cn http://www.morning.knqck.cn.gov.cn.knqck.cn http://www.morning.jqjnx.cn.gov.cn.jqjnx.cn http://www.morning.lmrjn.cn.gov.cn.lmrjn.cn http://www.morning.nwynx.cn.gov.cn.nwynx.cn http://www.morning.btypn.cn.gov.cn.btypn.cn http://www.morning.ltfnl.cn.gov.cn.ltfnl.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.gjxr.cn.gov.cn.gjxr.cn http://www.morning.mhnr.cn.gov.cn.mhnr.cn http://www.morning.brwnd.cn.gov.cn.brwnd.cn http://www.morning.nlffl.cn.gov.cn.nlffl.cn http://www.morning.bpmtq.cn.gov.cn.bpmtq.cn http://www.morning.kpxky.cn.gov.cn.kpxky.cn http://www.morning.ntqgz.cn.gov.cn.ntqgz.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.fbjqq.cn.gov.cn.fbjqq.cn http://www.morning.trfrl.cn.gov.cn.trfrl.cn http://www.morning.jtsdk.cn.gov.cn.jtsdk.cn
