HDU-1856，并查集

本文主要是介绍HDU-1856，并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刚学并查集，这题还TLE几次了。关键是没优化。

代码：

#include<stdio.h>
#define N 10000001
int father[N];
int sum[N];int find(int x)
{return x==father[x]?x:find(father[x]);
}int main()
{int t,max,n,m,i;while(scanf("%d",&t)!=EOF){for(i=1;i<=N;i++){father[i]=i;sum[i]=1;}max=1;while(t--){scanf("%d%d",&n,&m);n=find(n);m=find(m);if(n!=m){if(sum[n]>sum[m]){int s=n;n=m;m=s;}    father[n]=m;                //把元素小的合并到元素多的，查找父节点就节省时间。sum[m]+=sum[n];if(sum[m]>max)max=sum[m];}}printf("%d\n",max);}return 0;
}

这篇关于HDU-1856，并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---