题目描述

某学校有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
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

讯享网

方法1：

这是第一种方法，此方法主题思路是以空间换时间的方法来进行运算；
即使不用O2，O3优化仍然能过，

#pragma GCC optimize(2)//O2，O3加速 #pragma GCC optimize(3) #include<iostream> using namespace std; #define N  int p[N],d[N];//每个始组的子孙数，即每个集合的人数 int chux[N],st[N];//chux[N]:每个输入的数是否出现，st[N]:用于最终操作，用来判断当前始祖是否出现过， int q[N],tt=-1;//用来存储输入过的数；（模拟栈） int q1[N],t1=-1;//用来存储进行完所有操作后，出现过的最终祖先（始祖）（即每个集合）；（模拟栈） int find(int x) { return p[x]==x?x:p[x]=find(p[x]); //也可以用常规的迭代法求祖宗（始祖），因为此算法已经优化可以用常规算法求时间了（即使不开O2优化也能过）； //while(p[x]!=x)x=p[x]; return x; } int Charu(int a,int b) { int t1=find(a); int t2=find(b); p[t1]=t2;//使得b的祖先成为 a的祖先的祖先； p[a]=t2;//同时使得b的祖宗直接变成a的祖宗 //这样下次搜寻a的祖先时，直接搜到b的祖先，节省时间 } int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)p[i]=i; for(int i=1;i<=m;i++) { int k,fis;scanf("%d%d",&k,&fis); if(!chux[fis])chux[fis]++,q[++tt]=fis;//如果第一个数从来没出现过，则标记下这个数，同时存入栈q for(int j=1;j<k;j++) { int x;scanf("%d",&x); if(!chux[x])chux[x]++,q[++tt]=x;//如果这个数从来没出现过，则标记下这个数，同时存入栈q Charu(x,fis);// 使第一个数的祖宗（始祖）成为这一行所有数的祖宗（始祖）的祖宗（始祖） } } for(int i=0;i<=tt;i++)//tt+1是本次输入中所有出现过的数（同学）； { int x=find( q[i] );//用x代替find(q[i])的原因，是因为防止多层数组嵌套发生越界现象 if( !st[x] )st[x]++,q1[++t1]=x;//祖宗x未出现过，则标记x，并存入栈q1 d[x]++;//该集合人数加1； } int maxx=0; for(int i=0;i<=t1;i++) { int x=q1[i]; if(d[ x ]>maxx)maxx=d[ x ];//找到最大集合的人数 } printf("%d",maxx); return 0; } 

讯享网

方法2

第二种方法就是简单的合并集合找祖先的算法，速度有点慢；
第二种方法参考https://blog.csdn.net/weixin_/article/details/?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%9C%8B%E5%8F%8B%E5%9C%88PTA&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-1-.142v83insert_down1,239v2insert_chatgpt&spm=1018.2226.3001.4187

讯享网#pragma GCC optimize(2) #pragma GCC optimize(3) #include<iostream> using namespace std; #define N  int p[N],d[N];//每个始组的子孙数，即每个集合的人数 int find(int x) { return p[x]==x?x:p[x]=find(p[x]); //此算法有点慢，只能用这种找祖宗的方法才能过 } int Charu(int a,int b) { int t1=find(a); int t2=find(b); p[t1]=t2;//使得b的祖先成为 a的祖先的祖先； } int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)p[i]=i; for(int i=1;i<=m;i++) { int k,fis;scanf("%d%d",&k,&fis); for(int j=1;j<k;j++) { int x;scanf("%d",&x); Charu(x,fis);// 使第一个数的祖宗（始祖）成为这一行所有数的祖宗（始祖）的祖宗（始祖） } } int maxx=0; for(int i=1;i<=n;i++) { maxx=max(maxx,++d[find(i)]);//找到最大集合的人数 //等效为：d[find(i)]++,maxx=max(maxx,d[ find(i) ]); } printf("%d",maxx); return 0; }