首页 > 代码库 > 6个朋友
6个朋友
http://codevs.cn/problem/2832/
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有这么一种说法：认识6个人，你就认识全世界的人。
Aiden现在有一张关系图，上面记载了N个人之间相互认识的情况。Aiden想知道，他能否只认识6个人就能间接认识这N个人呢？
输入描述 Input Description
第一行，两个数N，M，表示有N个人，M对认识关系。
接下来的M行，每行两个数ai，bi，表示ai与bi相互认识。
不保证认识关系不出现重复，保证ai≠bi。
N个人的编号为1...N。
输出描述 Output Description
若只认识6个人就能间接认识这N个人，则输出“^_^”。
若不行，则第一行输出“T_T”，第二行输出认识6个人最多能间接认识的人的个数。
输出不包括引号。
样例输入 Sample Input
6 7
1 2
1 3
2 4
3 5
4 6
5 6
3 2
样例输出 Sample Output
^_^
数据范围及提示 Data Size & Hint
对于30%的数据，保证0＜n≤1000。
对于50%的数据，保证0＜n≤5000。
对于100%的数据，保证0＜n≤10000，m≤10*n。
#include <algorithm>#include <iostream>#include <cstdio>using namespace std;int n,m,x,ans,sum,a,b;int fa[100015],num[100015];int find(int x){ if(fa[x]!=x) x=find(fa[x]); return x;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { cin>>a>>b; fa[find(a)]=find(b); } for(int i=1;i<=n;i++) num[find(i)]++; for(int i=1;i<=n;i++) if(num[i]) sum++; if(sum<=6) cout<<"^_^"; else { sort(num+1,num+n+1); for(int i=n;i>=n-5;i--) ans+=num[i]; cout<<"T_T"<<endl; cout<<ans; } return 0;}
6个朋友
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。