题目地址: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 ",max); } return 0; }
劣质的代码,天啦,晒出来求各位指点啊,图论完全是弱项啊
版权声明:本文为博主原创文章,未经博主允许不得转载。