C代码,(1)输入说明:输入的第1行包含两个正整数N(N<30000)和M(M<1000),分别代表学校的学生总数和俱乐部的个数。随后的M行每行按以下格式给出1个俱乐部的信息,其中1-N代表学生编号: 第i个俱乐部的人数Mi(空格)学生1(空格)学生2……学生Mi。 (2)输出说明:输出一个整数,表示最大朋友圈有多少人。
时间: 2023-12-06 22:41:07 浏览: 109
以下是一个可能的解法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 30000
#define MAX_M 1000
int N, M;
int friend[MAX_N + 1]; // 记录每个人的朋友圈编号
int size[MAX_N + 1]; // 记录每个朋友圈的大小
int find(int x) {
if (friend[x] == x) {
return x;
} else {
return friend[x] = find(friend[x]);
}
}
void union_set(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
friend[fa] = fb;
size[fb] += size[fa];
}
}
int main() {
scanf("%d%d", &N, &M);
// 初始化每个人的朋友圈编号和每个朋友圈的大小
for (int i = 1; i <= N; i++) {
friend[i] = i;
size[i] = 1;
}
// 处理每个俱乐部的信息
for (int i = 0; i < M; i++) {
int mi;
scanf("%d", &mi);
int first_member;
scanf("%d", &first_member);
for (int j = 1; j < mi; j++) {
int member;
scanf("%d", &member);
union_set(first_member, member);
}
}
// 找到最大的朋友圈
int max_size = 0;
for (int i = 1; i <= N; i++) {
if (friend[i] == i && size[i] > max_size) {
max_size = size[i];
}
}
printf("%d\n", max_size);
return 0;
}
```
解释如下:
首先定义了两个数组 `friend` 和 `size`,分别记录每个人的朋友圈编号和每个朋友圈的大小。
接下来读入输入,对每个俱乐部的成员进行合并操作。具体地,对于每个俱乐部,从第二个成员开始,依次将其与第一个成员所在的朋友圈合并,合并后更新朋友圈的大小。
最后遍历每个人,找到每个人所在的朋友圈的代表元(即 `friend[i] == i`),并更新最大的朋友圈大小。输出最大朋友圈的大小即可。