C编写,(1)输入说明:输入的第1行包含两个正整数N(N<30000)和M(M<1000),分别代表学校的学生总数和俱乐部的个数。随后的M行每行按以下格式给出1个俱乐部的信息,其中1-N代表学生编号: 第i个俱乐部的人数Mi(空格)学生1(空格)学生2……学生Mi。 (2)输出说明:输出一个整数,表示最大朋友圈有多少人。 测试实例: 1):输入: 7 4 3 1 2 3 2 1 4 3 5 6 7 1 6 输出:4 2):输入: 10 1 1 7 输出:1
时间: 2023-07-27 11:05:45 浏览: 176
这道题可以用并查集来解决。我们先将每个学生看成一个单独的集合,然后逐个读入俱乐部信息,将每个俱乐部内的学生合并到同一个集合中。最终,所得到的所有集合中,最大的集合的大小就是最大朋友圈的人数。
以下是完整的 C 代码实现:
```c
#include <stdio.h>
#define MAXN 30000
#define MAXM 1000
int father[MAXN + 1]; // 并查集数组
int cnt[MAXN + 1]; // 每个集合的大小
int n, m;
// 查找 x 所在集合的代表元素
int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
// 合并 x 和 y 所在的两个集合
void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
father[fx] = fy;
cnt[fy] += cnt[fx];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
father[i] = i;
cnt[i] = 1;
}
for (int i = 0; i < m; i++) {
int k, x, y;
scanf("%d%d", &k, &x);
for (int j = 1; j < k; j++) {
scanf("%d", &y);
merge(x, y);
}
}
int max_cnt = 0;
for (int i = 1; i <= n; i++) {
if (father[i] == i && cnt[i] > max_cnt) {
max_cnt = cnt[i];
}
}
printf("%d\n", max_cnt);
return 0;
}
```
代码思路:
1.首先定义一个并查集数组 father 和一个每个集合大小的数组 cnt,大小都为 n。
2.读入 n 和 m,初始化 father 和 cnt 数组,每个学生单独成一个集合,即 father[i]=i,cnt[i]=1。
3.按照题目要求,逐个读入俱乐部信息,对于每个俱乐部内的学生,将其合并到同一个集合中,即调用 merge 函数。
4.最后遍历一遍 father 数组,计算出每个集合的大小 cnt[i],并找到其中最大的值,即为最大朋友圈的人数。
5.输出最大朋友圈的人数。
阅读全文