首页 > 代码库 > 10608 - Friends
10608 - Friends
题目来源:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1549
并查集,求出每个friends集合,然后再计算每个集合friends个数,求出最大个数。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 const int maxn=30000+5; 5 int b[maxn],num[maxn]; 6 void init(int n) 7 { 8 for(int i=1;i<=n;i++) 9 b[i]=i;10 }11 int find_father(int x)12 {13 while(b[x]!=x){14 x=b[x];15 }16 return x;17 }18 void fri_union(int friA,int friB)19 {20 while(b[friA]!=friA){21 friA=b[friA];22 }23 while(b[friB]!=friB){24 friB=b[friB];25 }26 if(friB!=friA)27 b[friB]=friA;28 }29 int main()30 {31 int t;32 scanf("%d",&t);33 while(t--){34 int n,m,friA,friB;35 scanf("%d%d",&n,&m);36 init(n);37 memset(num,0,sizeof(num));38 for(int i=1;i<=m;i++){39 scanf("%d%d",&friA,&friB);40 fri_union(friA,friB);41 }42 for(int i=1;i<=n;i++){43 int father=find_father(i);44 num[father]++;45 }46 std::sort(num,num+n);47 printf("%d\n",num[n-1]);48 }49 return 0;50 }
10608 - Friends
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。