(1)输入说明:输入的第1行包含两个正整数N(N<30000)和M(M<1000),分别代表学校的学生总数和俱乐部的个数。随后的M行每行按以下格式给出1个俱乐部的信息,其中1-N代表学生编号: 第i个俱乐部的人数Mi(空格)学生1(空格)学生2……学生Mi。 (2)输出说明:输出一个整数,表示最大朋友圈有多少人。
时间: 2023-12-06 16:41:09 浏览: 124
这道题可以使用并查集来解决。
首先,我们需要定义每个学生的父节点,即每个人所属的朋友圈的代表元素。一开始,每个人的父节点都是他自己。
然后,我们遍历每个俱乐部,将俱乐部中的学生们加入同一个朋友圈中。具体地,我们将俱乐部中的第一个学生作为代表元素,然后依次将其他学生的父节点设为这个代表元素。
最后,我们遍历每个人,找到他所在朋友圈的代表元素,然后统计该代表元素中有多少人,即为该朋友圈的人数。我们取所有朋友圈中最大的人数作为最大朋友圈的人数。
下面是AC代码:
相关问题
C代码,(1)输入说明:输入的第1行包含两个正整数N(N<30000)和M(M<1000),分别代表学校的学生总数和俱乐部的个数。随后的M行每行按以下格式给出1个俱乐部的信息,其中1-N代表学生编号: 第i个俱乐部的人数Mi(空格)学生1(空格)学生2……学生Mi。 (2)输出说明:输出一个整数,表示最大朋友圈有多少人。
以下是一个可能的解法:
```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`),并更新最大的朋友圈大小。输出最大朋友圈的大小即可。
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
这道题可以用并查集来解决。我们先将每个学生看成一个单独的集合,然后逐个读入俱乐部信息,将每个俱乐部内的学生合并到同一个集合中。最终,所得到的所有集合中,最大的集合的大小就是最大朋友圈的人数。
以下是完整的 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.输出最大朋友圈的人数。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)