本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6048. 家庭问题 - AcWing题库【题目描述】有n nn个人编号分别为1 , 2 , … , n 1,2,\dots,n1,2,…,n另另外还知道存在K KK个关系。一个关系的表达为二元组( α , β ) (\alpha,\beta)(α,β)形式表示α , β \alpha,\betaα,β为同一家庭的成员。问题当n , k n,kn,k和k kk个关系给出之后求出其中共有多少个家庭、最大的家庭中有多少人。例如n 6 n6n6k 3 k3k3三个关系为( 1 , 2 ) (1,2)(1,2)( 1 , 3 ) (1,3)(1,3)( 4 , 5 ) (4,5)(4,5)此时6 66个人组成三个家庭即{ 1 , 2 , 3 } \{1,2,3\}{1,2,3}为一个家庭{ 4 , 5 } \{4,5\}{4,5}为一个家庭{ 6 } \{6\}{6}单独为一个家庭第一个家庭的人数最多。【输入】文件的第一行为n , k n,kn,k二个整数接下来的k kk行每行二个整数用空格分隔表示关系。【输出】二个整数分别表示家庭个数和最大家庭人数。【输入样例】6 3 1 2 1 3 4 5【输出样例】3 3【解题思路】【算法标签】#图的遍历-BFS#【代码详解】#includebits/stdc.husingnamespacestd;// 定义常量 N 和 M分别表示节点数和边数的最大值constintN105,M1010*2;// 使用 vector 存储图的邻接表vectorinth[N];// 使用队列进行广度优先搜索queueintq;// 使用布尔数组记录节点是否被访问过boolst[N];// ans1 记录连通分量的数量ans2 记录最大的连通分量的大小intans1,ans2;// n 表示节点数m 表示边数intn,m;// 广度优先搜索函数返回从节点 x 开始的连通分量的大小intbfs(intx){ints1;// 初始化连通分量大小为 1q.push(x);// 将节点 x 入队st[x]true;// 标记节点 x 已访问while(!q.empty()){intndq.front();q.pop();// 取出队首元素并出队for(inti0;ih[nd].size();i){intjh[nd][i];// 获取相邻节点if(!st[j]){// 如果相邻节点未被访问过q.push(j);// 将相邻节点入队st[j]true;// 标记相邻节点已访问s;// 连通分量大小加 1}}}returns;// 返回连通分量的大小}intmain(){cinnm;// 输入节点数和边数for(inti1;im;i){inta,b;cinab;// 输入边的两个端点h[a].push_back(b);// 在邻接表中添加边 a - bh[b].push_back(a);// 在邻接表中添加边 b - a}for(inti1;in;i){if(!st[i]){// 如果节点 i 未被访问过ans1;// 连通分量数量加 1ans2max(ans2,bfs(i));// 更新最大连通分量的大小}}coutans1 ans2endl;// 输出连通分量的数量和最大连通分量的大小return0;}【运行结果】6 3 1 2 1 3 4 5 3 3