本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：6048. 家庭问题 - 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 n=6n=6，k = 3 k=3k=3，三个关系为：( 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#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;// 定义常量 N 和 M，分别表示节点数和边数的最大值constintN=105,M=1010*2;// 使用 vector 存储图的邻接表vector<int>h[N];// 使用队列进行广度优先搜索queue<int>q;// 使用布尔数组记录节点是否被访问过boolst[N];// ans1 记录连通分量的数量，ans2 记录最大的连通分量的大小intans1,ans2;// n 表示节点数，m 表示边数intn,m;// 广度优先搜索函数，返回从节点 x 开始的连通分量的大小intbfs(intx){ints=1;// 初始化连通分量大小为 1q.push(x);// 将节点 x 入队st[x]=true;// 标记节点 x 已访问while(!q.empty()){intnd=q.front();q.pop();// 取出队首元素并出队for(inti=0;i<h[nd].size();i++){intj=h[nd][i];// 获取相邻节点if(!st[j]){// 如果相邻节点未被访问过q.push(j);// 将相邻节点入队st[j]=true;// 标记相邻节点已访问s++;// 连通分量大小加 1}}}returns;// 返回连通分量的大小}intmain(){cin>>n>>m;// 输入节点数和边数for(inti=1;i<=m;i++){inta,b;cin>>a>>b;// 输入边的两个端点h[a].push_back(b);// 在邻接表中添加边 a -> bh[b].push_back(a);// 在邻接表中添加边 b -> a}for(inti=1;i<=n;i++){if(!st[i]){// 如果节点 i 未被访问过ans1++;// 连通分量数量加 1ans2=max(ans2,bfs(i));// 更新最大连通分量的大小}}cout<<ans1<<" "<<ans2<<endl;// 输出连通分量的数量和最大连通分量的大小return0;}【运行结果】
6 3 1 2 1 3 4 5 3 3
