[转帖]POJ 1611 The Suspects (并查集)_MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2002 | 回复: 0   主题: [转帖]POJ 1611 The Suspects (并查集)        下一篇 
genweihua
注册用户
等级:新兵
经验:72
发帖:2
精华:0
注册:2013-12-26
状态:离线
发送短消息息给genweihua 加好友    发送短消息息给genweihua 发消息
发表于: IP:您无权察看 2015-3-18 10:59:32 | [全部帖] [楼主帖] 楼主

简单并查集,没什么好说的。  题目连接:请戳这里。

题目大意:0一定是SARS,和SARS在一起的一定是SARS,求0~n-1中共有多少个SARS;

思路:回顾下并查集,顾名思义,并查集的作用不就的“并”和“查”嘛。并查集的功能描述为:合并两个集合;将一元素并入另一集体;判断两个元素是否属于同一个集合。

题目也是给你m个集合咯。所以很简单咯。

~~~~

01#include<iostream>


02#include<cstdio>


03#include<cstring>


04#include<cmath>


05#include<algorithm>


06#include<queue>


07#define N 30000+10


08usingnamespacestd;


09


10intf[N],Rank[N];


11voidInit(intn)


12{


13for(inti=0;i<n;i++)


14{


15f[i]=i;


16Rank[i]=1;


17}


18}


19intFind(intx)


20{


21returnf[x]==x?x:f[x]=Find(f[x]);  // ~.~


22}


23voidMerge(inta,intb)


24{


25intra=Find(a),rb=Find(b);


26if(ra==rb) return;


27elseif(Rank[ra]>Rank[rb])


28f[rb]=ra;


29elseif(Rank[ra]<Rank[rb])


30f[ra]=rb;


31else{


32f[rb]=ra;


33Rank[ra]++;


34}


35}


36intmain()


37{


38intn,m;


39while(scanf("%d %d",&n,&m),n m)


40{


41Init(n);


42for(inti=0;i<m;i++)


43{


44intk,s;


45scanf("%d %d",&k,&s);


46for(intj=1;j<k;j++)


47{


48intt;


49scanf("%d",&t);


50Merge(s,t);


51}


52}


53intans=1;


54for(inti=1;i<n;i++)    //不能用f[0]==f[i] ~.~


55if(Find(i)==Find(0)) ans++;


56printf("%d\n",ans);


57}


58return0;


59}


--转自 北京联动北方科技有限公司




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论