http://acm.hdu.edu.cn/showproblem.php?pid=1213
/*
并查集就是查找两个元素的根结点,并按规定通过这两个元素把两元素所在的集合合并。属于同一集合的元素通过查找函数得到的根结点是相同的,由此可判断两个元素是否同属一个集合。
确定根节点数:最后结果中,满足 Father[i]=i 的节点 i 为根节点;
判断是否有环:在 Union() 函数中,如果 x==y 则表示形成了一个环;
*/
#include<stdio.h>
#define Max 1000
int Father[Max+5],sum;
void Makeset(int n)//初始化记录父结点的数组
{
int i;
for(i=1;i<=n;i++)
Father[i]=i;
}
int Findset(int x)//查找元素的根结点
{
if(x!=Father[x])
Father[x]=Findset(Father[x]);//通过递归实现在查找过程中压缩路径
return Father[x];
}
void Union(int a,int b)//将两个元素所属的集合合并
{
int x=Findset(a);
int y=Findset(b);
if(x==y)
return;
sum--;
Father[y]=x;
}
int main()
{
int T,n,m,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
Makeset(n);
sum=n;
while(m--)
{
scanf("%d%d",&a,&b);
Union(a,b);
}
printf("%d\n",sum);
getchar();
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...
一、内容 TT and FF are ... friends. Uh... very very good friends -________-b FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game....
经典算法:(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)
本压缩包内包含杭电ACM集训的课件PPT,较为详细的介绍了动态规划,计算几何,贪心算法, 搜索,二分图及其应用,母函数及其应用,组合博弈入门,并查集,递推求解等常用算法
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 ...poj2832 并查集边的计算 sgu218 hcraft 二分图匹配验证 二分答案
2012-06-11 16:03 0 1.txt 2012-06-11 15:20 42,528 c#仿QQ好友界面.rar 2012-06-11 15:22 216,281 ChineseChessV1.rar ...2012-06-11 15:38 299,008 (HDUACM2010版_06)并查集(最小生成树).ppt