某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：
第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi
输出给出一个整数，表示在最大朋友圈中有多少人。
#include <stdio.h>#include<stdlib.h>/* 评测结果 时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户2016-08-30 09:30 答案正确 25 5-25 gcc 12 1 569985011测试点结果 测试点 结果 得分/满分 用时（ms） 内存（MB）测试点1 答案正确 18/18 2 1测试点2 答案正确 2/2 1 1测试点3 答案正确 5/5 12 1查看代码*/typedef struct node *Students;struct node { int identifier; int pub;};/*对每个学生所归属的多个pub进行合并。合并到最后，那个最大的pub就是要查询的最大朋友圈了*/
int main() { int n;//<=30000学生人数 int m;//<=1000俱乐部的个数 scanf("%d%d",&n,&m); int Students[30001]; for(int i=0; i<n; i++) { Students[i+1]=-1; } int Pubs[1001]; for(int i=0; i<m; i++) { Pubs[i]=i; }
for(int i=0; i<m; i++) { int members; int flag=i; scanf("%d",&members); while(members--) { int Eachmember; scanf("%d",&Eachmember); if(Students[Eachmember]==-1) {//对于没有组织的学生进行入会登记 Students[Eachmember]=flag; } else { //对老油条，调整pub的父节点,同时修改flag为当前发现的最先pub// printf("[%d-S%d]",i,Eachmember); int parents=Pubs[i]<Pubs[Students[Eachmember]]?Pubs[i]:Pubs[Students[Eachmember]]; Pubs[i]=parents; Pubs[Students[Eachmember]]=parents; flag=parents; } } }for(int i=0;i<n;i++){//复查 Students[i]=Pubs[Students[i]];}int MostFriends=0;for(int i=0;i<m;i++){ if(Pubs[i]!=i)continue;// printf("\npub%d:",i); int Friends=0; for(int j=1;j<=n;j++){// printf("%d ",j); if(Students[j]==i)Friends++; } if(Friends>MostFriends)MostFriends=Friends;}printf("%d",MostFriends);
return 0;}
//Students Creat(int n){// Students temp=(Students)malloc(sizeof(struct node)*n);// for(int i=0;i<n;i++){// temp[i].identifier=i;//// }//}
转载于:https://www.cnblogs.com/linguiquan/p/9050034.html
相关资源：图的深度优先遍历和广度优先遍历算法