社团分组题解
2026-07-22 20:03:48
发布于：广东
熟人分组题解
题目大意
一共有 N 名同学，编号为 1 ~ N。
题目给出 M 条关系，每条关系为：
x y
表示同学 x 和同学 y 属于同一个熟人圈。
熟人关系具有传递性。
例如：
1和2属于同一个熟人圈；2和3属于同一个熟人圈；
那么 1、2、3 都属于同一个熟人圈。
现在要把所有同学分成若干组，并且要求：
同一个熟人圈中的任意两名同学不能被分到同一组。
求至少需要多少组。
一、如何理解这道题
我们可以把每一名同学看成一个点。
如果两名同学属于同一个熟人圈，就在他们之间连接一条边。
例如关系为：
1 2
2 5
3 4
可以画成：
1 —— 2 —— 5
3 —— 4
因此可以得到两个熟人圈：
熟人圈 1：1、2、5
熟人圈 2：3、4
在图论中，一个熟人圈就是一个连通块。
所谓连通块，可以简单理解为：
从其中任意一个点出发，沿着边可以到达这个集合中的所有点。
二、为什么答案是最大的熟人圈人数
假设有两个熟人圈：
熟人圈 1：1、2、5
熟人圈 2：3、4
第一个熟人圈有 3 个人。
因为同一个熟人圈中的任意两个人都不能放在同一组，所以 1、2、5 必须分别放进不同的组。
因此至少需要 3 组：
第 1 组：1
第 2 组：2
第 3 组：5
第二个熟人圈只有 2 个人，他们可以放入前面已经建立的组中：
第 1 组：1、3
第 2 组：2、4
第 3 组：5
这是合法的，因为 1 和 3 不属于同一个熟人圈，2 和 4 也不属于同一个熟人圈。
所以：
不同熟人圈可以重复使用相同的组。
因此，只需要找到人数最多的熟人圈。
如果最大的熟人圈有 k 个人，那么答案就是 k。
三、解题思路
我们使用邻接表保存同学之间的关系。
vector<int> a[N];
其中：
a[x]
保存所有与同学 x 有直接关系的同学。
因为同学关系是双向的，所以输入一条关系 x y 时，需要添加两条边：
a[x].push_back(y);
a[y].push_back(x);
接下来枚举每一名同学。
如果某名同学还没有被访问过，就从这名同学开始进行一次深度优先搜索。
一次完整的深搜可以找到一个完整的熟人圈。
在深搜过程中，每访问到一名新的同学，就让：
sum++;
深搜结束后，sum 就是当前熟人圈的人数。
最后用：
ans = max(ans, sum);
记录最大的熟人圈人数。
四、深搜函数怎么写
深搜函数如下：
void dfs(int f) {
if(vis[f]) return;
vis[f] = true;
sum++;
for(int i = 0; i < a[f].size(); i++) {
dfs(a[f][i]);
}
}
下面逐句解释。
1. 判断当前同学是否已经访问过
if(vis[f]) return;
如果同学 f 已经被访问过，就直接返回。
这样可以防止重复搜索，也可以防止在无向图中无限递归。
例如存在一条边：
1 —— 2
从 1 搜索到 2 后，2 又能搜索回 1。
如果没有 vis 数组，就会变成：
1 -> 2 -> 1 -> 2 -> 1 -> 2 ...
程序会一直递归下去。
2. 标记当前同学已经访问
vis[f] = true;
表示同学 f 已经被找到，以后不需要再次搜索。
3. 统计当前熟人圈的人数
sum++;
每第一次访问一名同学，就把当前熟人圈的人数加一。
这里的 sum++ 一定要放在访问节点的位置，而不能放在遍历边的位置。
4. 继续搜索与当前同学有关系的人
for(int i = 0; i < a[f].size(); i++) {
dfs(a[f][i]);
}
a[f] 中保存了所有与同学 f 有直接关系的人。
我们继续对这些人进行深搜，就可以找到整个熟人圈。
五、你的原代码有什么问题
你的深搜部分原来是：
void dfs(int f) {
if(vis[f] == 1) return;
vis[f] = 1;
for(int i = 0; i < a[f].size(); i++) {
dfs(a[f][i]);
sum++;
}
}
问题出在：
sum++;
你把它放在了遍历邻接表的循环里面。
这意味着：
每遍历一条边，
sum就加一。
但是我们需要统计的是熟人圈中的人数，而不是边数。
六、为什么统计边数是错误的
假设只有两名同学：
1 2
因为这是无向图，所以建立邻接表后会保存：
a[1] 中有 2
a[2] 中有 1
也就是：
1 -> 2
2 -> 1
虽然这个熟人圈中只有 2 个人，但是邻接表中有两条记录。
而且题目允许重复输入关系。
例如：
1 2
1 2
1 2
实际上仍然只有两名同学属于这个熟人圈。
但是邻接表中会保存很多条重复边。
如果按照边数进行统计，答案就会错误。
因此应该写成：
void dfs(int f) {
if(vis[f]) return;
vis[f] = true;
sum++;
for(int i = 0; i < a[f].size(); i++) {
dfs(a[f][i]);
}
}
也就是：
每访问到一名新的同学时，才让
sum加一。
七、完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> a[N];
bool vis[N];
int n, m;
int ans, sum;
void dfs(int f) {
// 已经访问过，不需要再次搜索
if(vis[f]) return;
// 标记当前同学已经访问
vis[f] = true;
// 当前熟人圈人数加一
sum++;
// 搜索与当前同学有关系的所有同学
for(int i = 0; i < a[f].size(); i++) {
dfs(a[f][i]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
while(m--) {
int x, y;
cin >> x >> y;
// 无向图需要添加双向边
a[x].push_back(y);
a[y].push_back(x);
}
// 枚举每一名同学
for(int i = 1; i <= n; i++) {
// 如果没有访问过，说明发现了一个新的熟人圈
if(!vis[i]) {
// 重新统计当前熟人圈的人数
sum = 0;
// 深搜找到整个熟人圈
dfs(i);
// 更新最大熟人圈人数
ans = max(ans, sum);
}
}
cout << ans << '\n';
return 0;
}
八、样例分析
输入：
5 3
1 2
3 4
5 1
建立的关系为：
1 —— 2
|
5
3 —— 4
程序首先从同学 1 开始深搜。
搜索顺序可能是：
1 -> 2 -> 5
所以第一个熟人圈的人数为：
sum = 3
然后继续枚举。
同学 2 已经访问过，同学 3 没有访问过，所以从同学 3 开始深搜：
3 -> 4
第二个熟人圈人数为：
sum = 2
因此：
ans = max(3, 2) = 3
最终输出：
3
九、为什么每次深搜前要把 sum 清零
sum 表示当前熟人圈的人数。
假设第一个熟人圈有 3 个人，搜索结束后：
sum = 3
接下来搜索第二个熟人圈之前，必须执行：
sum = 0;
否则第二个熟人圈的人数会继续加在第一个熟人圈后面。
正确写法是：
if(!vis[i]) {
sum = 0;
dfs(i);
ans = max(ans, sum);
}
十、没有关系的同学怎么处理
假设某名同学没有任何关系。
例如一共有三名同学，但是只有一条关系：
1 2
那么同学 3 自己也构成一个熟人圈。
程序枚举到同学 3 时，会执行：
sum = 0;
dfs(3);
进入 dfs(3) 后会执行：
sum++;
所以同学 3 所在的熟人圈大小为 1。
因此孤立的同学也可以被正确统计。
十一、重复关系会不会影响答案
题目中可能出现重复关系，例如：
1 2
1 2
2 1
这些关系都会被保存到邻接表中。
但是深搜中有：
if(vis[f]) return;
所以同一名同学只会在第一次访问时执行：
sum++;
之后即使通过重复边再次搜索到他，也会直接返回。
因此重复关系不会影响最终答案。
十二、正确性说明
每次从一个没有访问过的同学开始深搜，深搜会沿着关系边找到所有与他属于同一个熟人圈的同学。
每找到一名新的同学，就让 sum 加一，因此深搜结束后，sum 就是当前熟人圈的人数。
程序对每一个熟人圈都进行一次深搜，并使用 ans 保存最大的熟人圈人数。
同一个熟人圈中有多少人，就至少需要多少个不同的组。
不同熟人圈之间可以重复使用这些组。
所以最少组数等于最大熟人圈的人数。
因此程序输出的 ans 就是正确答案。
十三、复杂度分析
每名同学最多被深搜访问一次。
每条关系在无向图中会被检查两次。
因此时间复杂度为：
O(N + M)
邻接表和访问数组占用的空间复杂度为：
O(N + M)
十四、总结
这道题的对应关系为：
同学 -> 图中的点
关系 -> 图中的无向边
熟人圈 -> 图中的连通块
深度优先搜索 -> 找出一个完整的连通块
sum -> 当前连通块的人数
ans -> 最大连通块的人数
最关键的一点是：
sum++;
应该在第一次访问一个节点时执行，而不是每遍历一条边时执行。
因此答案就是：
最大的熟人圈人数
这里空空如也
有帮助，赞一个