用C++解决下述问题:描述 Xiao Ming is an art teacher. In his handicraft class, he wants to divide students into groups. For the group with the fewest students, he will help them complete the task. However, he only knows that student Si and Sj are in the same group. Can you help Xiao Ming find the group with the fewest students? 输入 The first line is an integer T (T<50), the number of test cases. For each test case, the first line are two integers N and M (1<=N, M<=1000). N is the number of students in Xiao Ming's class, and M is the number of pairs. Then M lines follow. Each line contains two integers Ai and Bi, meaning that students Ai and Bi are in the same group. 输出 For each test case, print the number of students in the group including the fewest students.
时间: 2024-03-09 17:49:42 浏览: 24
好的,这是一个关于图的问题,我们可以使用并查集来解决。以下是 C++ 的实现代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1010;
int fa[MAXN];
int find(int x) {
if (fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
while (m--) {
int a, b;
cin >> a >> b;
fa[find(a)] = find(b); // 将 a 和 b 合并到同一组
}
int cnt[MAXN];
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++) {
cnt[find(i)]++; // 统计每个集合中的元素个数
}
int ans = 1e9;
for (int i = 1; i <= n; i++) {
if (cnt[i] && cnt[i] < ans) ans = cnt[i]; // 找到最小的元素个数
}
cout << ans << endl;
}
return 0;
}
```
具体思路是:先将每个元素的父亲设为自己,然后对于每个输入的元素对 (a, b),将 a 和 b 的父亲合并到同一个集合中。最后统计每个集合中的元素个数,找到最小的元素个数即可。