本文主要是介绍HDU ACM 1856. More is better(并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/**********************************题目大意：把是朋友的人放到一组，求出人数最多的一组，并输出人数；
题目解析：运用并查集把有关系的人合并到一组，并且计算出此集合的结点数rank[i]；
把rank[i]与rank1比较大小，把值大的赋值给rank1，最后输出题目要求的结果rank1；
错误分析：1. 下面的1,比较大小放在Union中 ,可以减少运行时间，
2.定义 n,i,x,y;不能定义为全局变量，否则不能输出结果，至于为什么我也不懂，求解？
*********************************/
#include<cstdio>
#include<iostream>
using namespace std;
#define M 100005
int father[M],rank[M];
//father[i]为i的父结点，rank[i]为i所属集合的总元素数
void init(void)
//初始化
{
int i;
for(i=1;i<=M;i++)
{
father[i]=i;
// 各个元素独自构成一个集合
rank[i]=1;
}
}
int find(int x)
//查找根结点
{
if(x!=father[x])
father[x]=find(father[x]);
// 压缩路径，减少查询时运行的时间，使结点都指向根结点；
return father[x];
}
int Union(int x,int y,int rank1)
// 合并
{
x=find(x);
//查找x的根结点
y=find(y);
if(x!=y)
//若两个x,y的根结点不同（即两个元素不再一个集合中），则合并两个集合
{
father[x]=y;
rank[y]+=rank[x];
if(rank1<rank[y])
/*1.判断合并后的集合内元素总数是否大于其他集合总数
找出含元素最多的集合*/
rank1=rank[y];
}
return rank1;
}
int main()
{
int n,i,x,y;
while(scanf("%d",&n)!=EOF)
{
init();
int rank1=1;
while(n--)
{
scanf("%d %d",&x,&y);
rank1=Union(x,y,rank1);
}
printf("%d\n",rank1);
//输出元数最多的集合
}
return 0;
}
这篇关于HDU ACM 1856. More is better(并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
