题目地址：http://haut.openjudge.cn/20131112/6/
求编号最多的组
- 总时间限制:
- 1000ms
- 内存限制:
- 63353kB
- 描述
相邻两个数属于同一组，例如
1 2
3 5
2 6
4 7
9 61-2-6-9为一组
3-5为一组
4-7为一组
所以最多元素的组为4
- 输入
- 多组数据，每组第一行两个正整数n,m，表示有1~n这n个编号，m个关系。
接下来m行，每行两个数i, j， 1 <= i, j <= n，表示i和j是一组的。
每个编号自己和自己是一组的。
1 < n < 1000000 ，1 < m < 100000 - 输出
- 每组数据输出一行，一个数，表示组员最多的组的组员个数
- 样例输入
10 5
1 2
3 5
2 6
4 7
9 6- 样例输出
4
#include<stdio.h>
#include<string.h>
int father[1000002],a,b,m,n,i,d=0,max=0;
int family[1000002]; int find(int x){
if (father[x]!=x) father[x]=find(father[x]);
return father[x];
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
max=0;
for (i=1;i<=n;i++) {
father[i]=i;
family[i]=0;
}
for (i=1;i<=m;i++){
scanf("%d%d",&a,&b);
a=find(a);
b=find(b);
father[a]=b;
}
for (i=1;i<=n;i++) {
family[find(i)]++;
if(family[find(i)]>max)max=family[find(i)];
}
printf("%d\n",max);
}
return 0;
}
劣质的代码，天啦，晒出来求各位指点啊，图论完全是弱项啊
版权声明：本文为博主原创文章，未经博主允许不得转载。