[转帖]POJ 1611 The Suspects (并查集)_MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛

总帖数

每页帖数

1/1页

返回列表

发起投票

查看: 2203 | 回复: 0

主题： [转帖]POJ 1611 The Suspects (并查集)

genweihua

注册用户

等级：新兵
经验：72
发帖：2
精华：0
注册：2013-12-26
状态：离线
发送短消息息给genweihua

加好友发送短消息息给genweihua

发消息

发表于：

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

08	usingnamespacestd;

10	intf[N],Rank[N];

11	voidInit(intn)

{

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

{

f[i]=i;

16	Rank[i]=1;

}

19	intFind(intx)

{

21	returnf[x]==x?x:f[x]=Find(f[x]); // ～．～

}

23	voidMerge(inta,intb)

{

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

26	if(ra==rb) return;

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

f[rb]=ra;

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

f[ra]=rb;

else{

f[rb]=ra;

33	Rank[ra]++;

}

intmain()

{

intn,m;

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

{

Init(n);

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

{

intk,s;

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

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

{

intt;

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

50	Merge(s,t);

}

intans=1;

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

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

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

}

return0;

}

--转自

本版精华
热门帖子

操作引用/回复

总帖数

每页帖数

1/1页

返回列表

用户登录

Weblogic中间件技术论坛

Tuxedo中间件技术论坛

数据库论坛

Java论坛

Linux/unix论坛

网站地图