2832 6个朋友

时间限制: 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。

思路：并查集找出相同祖先的点，统计祖先有多少。

若小于6，可以；大于6，统计人数。

 1 #include<iostream>
 2 using namespace std;
 3 #include<cstdio>
 4 #include<algorithm>
 5 int far[10010],num[10010];
 6 int ans,sum,c,n,m;
 7 bool cmp(int a,int b)
 8 {
 9     return a>b;
10 }
11 int find(int a)
12 {
13     if(a!=far[a])far[a]=find(far[a]);
14     return far[a];
15 }
16 int main()
17 {
18     cin>>n>>m;
19     for(int i=1;i<=n;++i)far[i]=i;
20     for(int a,b,i=1;i<=m;++i)
21     {
22         scanf("%d%d",&a,&b);
23         int r=find(a);
24         int rr=find(b);
25         if(r!=rr)far[rr]=r;
26     }
27     for(int i=1;i<=n;++i)
28     {
29         int r=find(i);
30         if(r==i)ans++;
31         num[r]++;
32     }
33     if(ans<=6)cout<<"^_^";
34     else if(ans>6)
35     {
36         sort(num+1,num+n+1,cmp);
37         for(int i=1;i<=6;++i)
38         {
39             sum+=num[i];
40         }
41         cout<<"T_T"<<endl<<sum;
42     }
43     return 0;
44 }