首页 > 代码库 > HDU 1856 More is better
HDU 1856 More is better
http://acm.hdu.edu.cn/showproblem.php?pid=1856
题意：
王先生想要一些男孩帮助他做一个项目。因为项目相当复杂，男孩越多，越好。当然有一定的要求。
王先生选择了一个足够大的房间来容纳男孩。没有被选中的男孩必须立即离开房间。有10000000的男孩在房间号从1到10000000在一开始。王先生选择后，仍然在这个房间里的任何两个人应该是朋友（直接或间接），或者只剩下一个男孩。给定所有的直接朋友对，你应该决定最好的方法。
思路：
并查集。选出顶点数最多的并输出。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 #define N 10000000 7 8 int p[N], num[N], maxd; 9 10 void init()11 {12 int i;13 for (i = 1; i <= N; i++)14 {15 p[i] = i;16 num[i] = 1;17 }18 }19 20 int find(int x) 21 {22 if (p[x] != x)23 p[x] = find(p[x]);24 return p[x];25 }26 27 void merge(int a, int b)28 {29 int x = find(a);30 int y = find(b);31 if (x != y)32 {33 p[x] = y;34 num[y] += num[x];35 maxd = max(maxd, num[y]);36 }37 }38 39 int main()40 {41 //freopen("D:\\txt.txt", "r", stdin);42 int n, a, b;43 while (~scanf("%d", &n))44 {45 if (n == 0)46 {47 printf("1\n");48 continue;49 }50 maxd = 0;51 init();52 for (int i = 0; i<n; i++)53 {54 scanf("%d%d", &a, &b);55 merge(a, b);56 }57 printf("%d\n", maxd);58 }59 return 0;60 }
HDU 1856 More is better
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。