D - More is better

缺乏、安全感 2022-03-19 11:26 199阅读 0赞

### 题目描述： ###

Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. Of course there are certain requirements.

Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang’s selection any two of them who are still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.  
Input  
The first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤ 10000000)  
Output  
The output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep.  
Sample Input  
4  
1 2  
3 4  
5 6  
1 6  
4  
1 2  
3 4  
5 6  
7 8  
Sample Output  
4  
2

Hint  
A and B are friends(direct or indirect), B and C are friends(direct or indirect),  
then A and C are also friends(indirect).

In the first sample \{1,2,5,6\} is the result.  
In the second sample \{1,2\},\{3,4\},\{5,6\},\{7,8\} are four kinds of answers.

##### 题意： #####

一个房间里面有若干人。他们之间有些是朋友有些不是。现在从中选出一个群体（朋友的朋友也是朋友都是一个群体）。要使这个群体最大。  
现在输入他们之间的关系。  
第一行输入有多少个关系需要输入N。  
以下N行输入关系。  
输入1 2 。则表示1和2是朋友。  
分析：  
本题注意到Ｎ的范围是０到100000。也就是要对0时进行特判处理。在一开始的时候，我把输入0时，输出0。结果wa。  
后面一想房间里面肯定是有人的，那么只有当人数为1或者都是一个人一个群体时，之间才不会有关系。  
所以这点需要注意。所以本题用并查集在稍微加以变形即可得到答案。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
        using namespace std;
    int Find(int x,int f[])
    {
        if(x!=f[x])
            return f[x]=Find(f[x],f);
        return x;
    }
    int main()
    {
        int N;
        int f[100001];
        int vis[100001];
        while(~scanf("%d",&N))
        {
            if(N==0)
            {
                printf("%d\n",1);
                continue;
            }
            //初始化 vis数组也要初始化为0 用于后面统计 
            for(int i=1;i<=100000;i++)
            {
                vis[i]=0;
                f[i]=i;
            }
            for(int i=0;i<N;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                x=Find(x,f);y=Find(y,f);
                if(x!=y)
                    f[x]=y;
            }
            //这个循环的主要作用是将每个人都直接指向它的首领
            for(int i=1;i<=100000;i++)
                f[i]=Find(i,f);
              //通过遍历统计各个首领出现的次数  用到桶排知识 
            for(int i=1;i<=100000;i++)
            {
                int x=f[i];
                vis[x]++;
            }
            int Max=0;
            //遍历找出最多的
            for(int i=1;i<=100000;i++)
                if(Max<vis[i])
                   Max=vis[i];
            printf("%d\n",Max);
        }
    }