本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6058. 亲戚 - AcWing题库【题目描述】若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的某个人所在家族的人数。规定和 是亲戚 和 是亲戚那么 和 也是亲戚。如果 是亲戚那么 的亲戚都是 的亲戚 的亲戚也都是 的亲戚。具体来说一共涉及到n nn个人编号1 ∼ n 1\sim n1∼n接下来将依次进行m mm个操作操作分为以下两种M a b表示告知你a aa和b bb具有亲戚关系。Q a表示向你询问根据此前已经给定的所有信息可以确定的a aa所在的家族的人数。【输入】第一行包含两个整数n , m n,mn,m。接下来m mm行每行包含一个操作信息格式如题面描述。【输出】对于每个Q a操作输出一行结果一个整数表示当时可以确定的a aa所在的家族的人数。【输入样例】5 10 M 3 2 Q 4 M 1 2 Q 4 M 3 2 Q 1 M 3 1 Q 5 M 4 2 Q 4【输出样例】1 1 3 1 4【算法标签】#并查集#【代码详解】#includebits/stdc.husingnamespacestd;#defineN1000005intfa[N];// 并查集父节点数组intpeoNum[N];// peoNum[i]: 以i为根结点的集合的元素个数// 初始化并查集voidinitFa(intn){for(inti1;in;i){fa[i]i;// 每个结点初始化为自己的父节点peoNum[i]1;// 每个集合初始大小为1}}// 查找根节点带路径压缩intfind(intx){if(xfa[x])// 如果x是自己的父节点{returnx;// 返回x}else{returnfa[x]find(fa[x]);// 递归查找并路径压缩}}// 合并两个集合voidmerge(inti,intj){intxfind(i);// i的根节点intyfind(j);// j的根节点if(xy)// 如果x, y已经在一个集合内直接返回{return;}fa[x]y;// x的双亲设为ypeoNum[y]peoNum[x];// 合并集合大小}intmain(){ios::sync_with_stdio(false);// 关闭C与C输入输出同步cin.tie(nullptr);// 解绑cin和cout加速输入charc;// 操作类型intn,m,a,b;// n: 人数, m: 操作数, a,b: 操作参数cinnm;// 输入人数和操作数initFa(n);// 初始化并查集for(inti1;im;i)// 处理每个操作{cinc;// 输入操作类型if(cM)// 合并操作{cinab;merge(a,b);// 合并a,b所在的集合}else// c Q查询操作{cina;coutpeoNum[find(a)]\n;// 输出a所在集合的人数}}return0;// 程序正常结束}【运行结果】5 10 M 3 2 Q 4 1 M 1 2 Q 4 1 M 3 2 Q 1 3M 3 1 Q 5 1 M 4 2 Q 4