2905 - 我要组建军队
时间限制 : 1 秒
内存限制 : 128 MB
啊!几经周折.mty终于找到了他的偶像.他就是....fyc!
可是fyc这样的高级人士可不喜欢一个人总是缠着他.于是他出了一道难题想考考mty.fyc有几个手下:陈乐天,舒步鸡,胡巍......现在fyc要去和别人fight,需要组建一值军队.军队的士兵在fyc的手下里选.
要组建一个军队,必修满足军队中的每个人之间都有直接或间接的朋友关系.
那么mty现在需要组建一支在满足上述情况下的人数最多的军队.
问题规模:
对于100%的数据,1<=n<=1000,1<=m<=500.
题目输入
第一行,两个数,n,m.(n表示fyc有几个手下m表示有m对朋友关系).
一下m行,每行两个数.x[i],y[i].表示编号为x[i],y[i]的人是朋友.
题目输出
一个数,表示人数最多的军队的人数.
输入/输出样例
输入格式
5 3 1 2 2 3 3 4
输出格式
4
C++解答
#include<stdio.h> struct node{ int data; int rank; int parent; }; node t[1001]; int r[1000]; void set(node t[]){ int i; for(i=1;i<=1001;i++){ t[i].data=i; t[i].rank=0; t[i].parent=i; } } int find(node t[],int x){ if(x!=t[x].parent) return(find(t,t[x].parent)); else return x; } void un(node t[],int x,int y){ x=find(t,x); y=find(t,y); if(t[x].rank>t[y].rank){ t[y].parent=x; } else{ t[x].parent=y; if(t[x].rank==t[y].rank) t[y].rank++; } } int main(){ int m,a,b,N,mn=0,max=0; while(scanf("%d%d",&N,&m)!=EOF){ set(t); for(int i=0;i<m;i++){ scanf("%d%d",&a,&b); un(t,a,b); } for(int i=1,bb=0;i<=N;i++){ if(t[i].parent==i){ r[bb]=i; bb++; max++; } } int z=0; for(int p=0;p<max;p++){ for(int i=1;i<=N;i++){ if(find(t,i)==r[p]) mn++; } if(mn>=z) z=mn; mn=0; } printf("%d\n",z); } return 0; }