首页 技术 正文
技术 2022年11月23日
0 收藏 529 点赞 3,764 浏览 896 个字

某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出,如果A和B是朋友,且B和C是朋友,则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。

输入格式:

输入的第一行包含两个正整数N(≤≤30000)和M(≤≤1000),分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息,其中学生从1~N编号:

第i个俱乐部的人数Mi(空格)学生1(空格)学生2 … 学生Mi

输出格式:

输出给出一个整数,表示在最大朋友圈中有多少人。

输入样例:

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

输出样例:

4
并查集
include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string>
#include <map>
#include <algorithm>using namespace std;
int n,m;
int father[30005];
int find(int x)
{
if(father[x]!=x)
father[x]=find(father[x]);
else
return father[x];
}
int ans[30005];
int main()
{
scanf("%d%d",&n,&m);
int x;
int y;
for(int i=1;i<=n;i++)
father[i]=i;for(int i=1;i<=m;i++)
{
scanf("%d",&x);
int yy=0;
for(int j=1;j<=x;j++)
{
scanf("%d",&y);
if(yy!=0)
{
int fx=find(yy);
int fy=find(y);
father[fx]=fy;
}
else
yy=y;
}
}
for(int i=1;i<=n;i++)
{
int fa=find(i);
ans[fa]++;
}
sort(ans+1,ans+n+1);
printf("%d\n",ans[n]);
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141850.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,070
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,316
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,310
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,910
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,098
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站