首页 > > 程序设计 > C/C++ >

【rqnoj 343】mty的考验

2018-06-17 21:52:22来源：未知阅读 ()

题目描述

啊!几经周折.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
说明:1,2,3,4可组成一直军队.

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m,a,b,c[1005],fa[1005];
 6 int read(){
 7     int x=0,f=1;char ch=getchar();
 8     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
10     return x*f;
11 }
12 int find(int n){
13     if(fa[n]==n) return n;
14     else return fa[n]=find(fa[n]);
15 }
16 void unite(int x,int y){
17     fa[y]=x;
18 }
19 int main(){
20     n=read(),m=read();
21     for(int i=1;i<=n;i++) fa[i]=i;
22     for(int i=1;i<=m;i++){
23         a=read(),b=read();
24         unite(find(a),find(b));
25     }
26     int ans=0;
27     for(int i=1;i<=n;i++){
28         c[find(i)]++;
29         ans=max(ans,c[find(i)]);
30     }
31     printf("%d\n",ans);
32     return 0;
33 }