首页 > 代码库 > 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