yes you do
yes i do
posts - 4, comments - 2, trackbacks - 0, articles - 0
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2024年11月
>
日
一
二
三
四
五
六
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
数据结构
随笔档案
2009年8月 (1)
2009年5月 (3)
搜索
最新评论
1. re: PKU3468线段树入门
评论内容较长,点击标题查看
--T
2. re: PKU3468线段树入门
评论内容较长,点击标题查看
--lyb
阅读排行榜
1. PKU3468线段树入门(1495)
2. PKU2492 A Bug's Life(并查集)(293)
3. PKU1988Cube Stacking 并查(276)
4. 单链表反转程序(265)
评论排行榜
1. PKU3468线段树入门(2)
2. PKU1988Cube Stacking 并查(0)
3. 单链表反转程序(0)
4. PKU2492 A Bug's Life(并查集)(0)
PKU2492 A Bug's Life(并查集)
Posted on 2009-05-22 17:19
chenweiwei
阅读(293)
评论(0)
编辑
收藏
引用
并查集的简单变种
初始化
初始化的时候增加一个变题用来记录每只虫子的对立面。数组初始化均为-1,标志对立面未找到。
输入
查找两只虫子的对立面是否有记录,哪果有记录则将记录与输入的另一只虫子union,第二只虫子也这样操作。
判断
判断两足虫子是否为同性恋只需要判断他们的祖先是否一相同,如果相同则标记找到,如果不同按照上面的方法操作
想法
这道题最重要的是把同类合并,然后每次输入判断两只虫子是否在张图内,其中的技巧在于每次输入的两足虫子如果符合条件那们他们一定不在同一张图内,因为需要找另外一只虫子把他们加入的自己的那张图中,所以引入了opt这个数组。当然我也是参考了别人的程序,如果真的是实验比赛中恐怕很难想出这个方法。感谢提供了代码的先驱们。
void
Init(
int
nt)
//
初始化
{
for
(
int
i
=
0
; i
<=
nt;i
++
)
{
parent[i]
=
i;
rank[i]
=
0
;
opt[i]
=-
1
;
//
表示未找到对立面
}
}
//
判断是否出现同性恋
for
(i
=
0
;i
<
m;i
++
)
{
scanf(
"
%d %d
"
,
&
a,
&
b);
int
finda
=
FindSet(a);
int
findb
=
FindSet(b);
if
(finda
==
findb)flag
=
1
;
else
{
if
(opt[a]
!=-
1
)
{
UnionSet(opt[a],b);
}
if
(opt[b]
!=-
1
)
{
UnionSet(opt[b],a);
}
opt[a]
=
b;
opt[b]
=
a;
}
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © chenweiwei