并查集 基础 AC 2014-01-14 13:37 202人阅读 评论(0) 收藏...

题目地址：http://haut.openjudge.cn/20131112/6/

求编号最多的组

• 查看
• 提交
• 统计
• 提问

总时间限制: 

1000ms 

内存限制: 

63353kB

描述

相邻两个数属于同一组，例如

1 2
3 5
2 6
4 7
9 6

1-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; }

劣质的代码，天啦，晒出来求各位指点啊，图论完全是弱项啊

版权声明：本文为博主原创文章，未经博主允许不得转载。

转载于:https://www.cnblogs.com/you-well-day-fine/p/4671678.html

总结

以上是生活随笔为你收集整理的并查集 基础 AC 2014-01-14 13:37 202人阅读 评论(0) 收藏...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。