首页 > 代码库 > rqnoj343 mty的考验
rqnoj343 mty的考验
题目描述
啊!几经周折.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可组成一直军队.
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>using namespace std;const int maxn = 1050;int n,m;int f[maxn],sz[maxn];int findf(int x){ return x == f[x] ? x : f[x] = findf(f[x]);}int main(){ cin>>n>>m; for(int i = 1;i <= n;i++){ f[i] = i; sz[i] = 1; } int x,y,fx,fy; for(int i = 1;i <= m;i++){ scanf("%d%d",&x,&y); fx = findf(x); fy = findf(y); if(fx == fy) continue; //notice if(sz[fx] > sz[fy]) swap(fx,fy); sz[fy] += sz[fx]; f[fx] = fy; } int ans = 0; for(int i = 1;i <= n;i++){ if(ans < sz[i]) ans = sz[i]; } cout<<ans; return 0;}#include<iostream>using namespace std;int father[1001];int find(int x){ if(x!=father[x])father[x]=find(father[x]); return father[x];}void un(int f,int z){ father[z]=f;}int main(){ int a[1001]={0}; int ans=0; int n,m; int x,y; cin>>n>>m; for(int i=1;i<=n;i++) { father[i]=i; } for(int i=1;i<=m;i++) { cin>>x>>y; un(find(x),find(y)); } for(int i=1;i<=n;i++) { a[find(i)]++; ans=max(a[find(i)],ans); } cout<<ans; //system("pause"); return 0;}
rqnoj343 mty的考验
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。