14846: 朋友

14846: 朋友

时间限制: 1 Sec   内存限制: 128 MB

题目描述

有一个城镇，住着n个市民。已知一些人互相为朋友。引用一个名人的话说，朋友的朋友也是朋友。意思是说如果A和B是朋友，C和B是朋友，则A和C是朋友.你的任务是数出最大朋友组的人数。

输入

输入第一行由N，M组成，N是市民的个数（1<=n<=30000），m是朋友对的个数（0<=m<=500000）。下面的m行每一行由两个数A和B组成(1<=A,B<=N，A<>B)表示A和B是朋友。注意给的朋友对可能会有重复。

输出

输出仅有一行包含一个整数，表示要求的最大朋友组的人数。

样例输入 Copy

10 12

1 2

3 1

3 4

5 4

3 5

4 6

5 2

2 1

7 10

1 2

9 10

8 9

样例输出 Copy

6

并查集模板题，不详细解释。代码如下：

#include<bits/stdc++.h>

using namespace std;

int read(){

int x=0,f=0;char c=getchar();

while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

while(isdigit(c)){x=x*10+c-'0';c=getchar();}

return f?-x:x;

}

int n,m;

int fa[30005];

int num[30005];

int find_fa(int x){return x!=fa[x]?fa[x]=find_fa(fa[x]):x;}

void union_set(int x,int y){

int fx=find_fa(x),fy=find_fa(y);

fa[fx]=fy;

}

int main(){

n=read();m=read();

for(int i=1;i<=n;i++) fa[i]=i;

for(int i=1;i<=m;i++){

int x=read(),y=read();

union_set(x,y);

}

memset(num,0,sizeof(num));

for(int i=1;i<=n;i++) num[find_fa(i)]++;

int maxx=0;

for(int i=1;i<=n;i++) maxx=max(maxx,num[i]);

cout<<maxx<<endl;

return 0;

}