并查集专题【完结】

  1. 云栖社区>
  2. 博客>
  3. 正文

并查集专题【完结】

陈国林 2013-08-04 20:55:09 浏览592
展开阅读全文

个人整理 并查集


【poj】

第一题 poj 1182 食物链

点击打开链接poj 1182

思路: 带权并查集
分析:
1 典型的带权并查集的题目
2 如果x和y是同类的关系认为是0,如果是x吃y那么关系认为是1,那么x和y的关系为2就说明y吃x
3 那么如果x和y同类则rank[x] == rank[y] , 如果x吃y那么rank[x] == (rank[y]+1)%3 , 注意mod3的使用

点击查看代码


第二题 poj 1308 Is It A Tree?

点击打开链接 poj 1308

思路: 普通并查集
分析:
1 题目输入一些边,要我们去判断是否是一棵树
2 根据题目的意思,空树也是树或者只有一个跟节点的是树

3 不满足的情况是边是自环即x == y的情况,还有就是加入一条边形成环。由于树是一个连通分量,所以最后判断一下是不是只有一个连通分量

4 输入的边可能是自环,这个是一个trick

点击查看代码


第三题 poj 1611 The Suspects

点击打开链接poj 1611

思路: 普通并查集
分析:
1 题目最终要求的是和0同一个集合的元素的个数
2 比较简单的题,在线更新并查集,开个数组记录当前集合的元素的个数

点击查看代码


第四题 poj 1703 Find them, Catch them

点击打开链接poj 1703

思路: 简单带权并查集
分析:
1 题目要询问给定的x和y是否是同一个动物
2 我们假设如果不同,那么权值为1,否则为0。因此对于给定的x和y,那么如果x和y不在一个集合里面那么就是不确定,否则就可以根据rank来判断是什么关系

点击查看代码


第五题 poj 1988 Cube Stacking

点击打开链接 poj 1988

思路: 带权并查集
分析:
1 题目给定2种指令 M x y把x的集合放在y集合的上面,C x求x的下面有多少个元素
2 我们用rank[x]表示x以下有多少个元素,那么对于指令M x y我们始终把左边的合并到右边,那么这样rank就满足压缩的性质
3 但是因为这边的合并和普通不一样,它是把x所在的集合放在y所在集合上面,实际上是x的跟节点合并到y集合的最远点,所以我们应该开个数组记录当前集合最远的点
点击查看代码


第六题 poj 2236 Wireless Network

点击打开链接poj 2236

思路: 普通并查集
分析:
1 初始值所有的电脑都是坏的,然后给肯定n个点的坐标,只有距离不大于d的才认为连通的
2 现在给定两种操作,O p表示编号为p的电脑被修好了,S p q询问p q是否是连通的
3 简单的并查集,先预处理出所有的点到其他点的距离,然后每一次修好一个电脑之后就去更新并查集,遇到询问的时候只要判断是否在同一个集合里面即可

点击查看代码


第七题 poj 2492 A Bug's Life

点击打开链接poj 2492

思路: 带权并查集
分析:
1 用rank[i] = 0表示关系相同,用rank[i] = 1表示关系不同
2 在输入的时候把两个元素之间的关系建立起来,然后判断当前的两个元素是否在同一个集合里面,如果是则判断是不是属于同一个类型即可

点击查看代码


第八题 poj 2524 Ubiquitous Religions

点击打开链接poj 2524

水题

点击查看代码


第九题 poj 1456 Supermarket
点击打开链接poj 1456
思路: 贪心+并查集
分析:
1 题目的意思是给定n个物品的利润和出售的最后时间,求最大的利润
2 比较明显的贪心问题,按照利润排序,假设当前是第i个物品,那么利润为pi出售的时间为di,那么假设di还没有物品销售那么肯定先销售第i个物品,否则找di~1这些时间里面是否有没有销售物品
3 如果按照2的思路做法最坏的情况是O(n^2),但是数据比较弱可以过。但是我们这边可以利用并查集来优化,根据2如果di已经被占用了那么我们要去找di~1的时间,这里利用并查集的思路。如果di被占用了之后,那么father[di] = di-1说明如果下次再来一个销售日期为di的话是要放到di-1天,那么对于第i个物品我们只要判断find(di)是不是大于0,如果是di可以放到find(di)这一天销售,否则跳过

点击查看代码


第10题 poj 1733 Parity game

点击打开poj 1733

思路: 带权并查集
分析:
1 题目给定n个条件,要我们找到第一个不满足条件的编号
2 每一个条件给的是区间[l,r]的1的奇偶数,很明显[l,r]这个区间的1的个数可以由[0,r]-[0,l-1]得来
3 那么我们利用并查集的思想,rank[x]表示的是x到跟节点这个区间即[x,father[x]]这个区间的1的个数,那么奇偶性可以由1和0来表示
4 题目还有一个难点就是要离散化,一般的离散化的步骤是排序+去重,然后找的时候利用二分即可

点击查看代码


第十一题 poj 2912 Rochambeau

点击打开poj 2912

思路: 带权并查集
分析:
1 有n个小孩玩游戏,里面有一个入是裁判,剩下的人分为三组。现在我们既不知道裁判是谁也不知道分组的情况。现在n个小孩玩剪刀石头布,已知每组的小孩只会出同一种手势,问谁是裁判
2 题目说了输入=的时候说明是同一组,如果是<或>的时候说明是不同一组,那么根据食物链那一题的思路,我们设rank[x]表示x和根节点的关系,如果是=那么rank[x] = 0,如果是<则rank[x] = 1,否则为rank[x] = 2
3 剩下的就是怎么求最少几轮得到裁判的编号,要得出最后的裁判,也就是其他的人度不满足的最大的那一轮,因为那一轮过后就能确定裁判了
4 判断关系的时候,如果是不同的集合那就合并,否则判断是否有rank[x] == (rank[y]+val)%3

点击查看代码


【hdu】

第一题 hdu 3038 How Many Answers Are Wrong

点击打开hdu 3038

思路: 带权并查集
分析:
1 给定一序列的区间的和,求错误的个数
2 典型的带权并查集,区间[l,r]的和等于sum[r]-sum[l-1]。对于一般涉及到区间和还有个数的问题的时候,都要把左下标减一来处理
3 用rank[x]表示的是x到跟节点的和即[x,find(x)]的和,那么对于给定的x,y,val,fx为x的跟节点,fy为y的跟节点
如果fx != fy那么这个时候就要考虑fx和fy的关系
fx > fy ,则father[fy] = fx; rank[fy] = rank[x]-val-rank[y];
fx < fy ,father[fx] = fy; rank[fx] = rank[y]+val-rank[x];
否则判断rank[x]-rank[y]是否为val

点击查看代码


第二题 hdu 1856 More is better

点击打开链接hdu 1856

思路: 离散化+并查集
分析:
1 点数最多为10^7,但是边数最多10^5,所以我们必须采用离散化,然后利用带权并查集的思想,rank[x]表示的是以x为根节点的集合的元素个数
2 这一题主要注意的就是当n = 0的时候,因为题目说了刚开始有10^7个人在房间里面,所以n = 0的时候最多有一个人出去
点击查看代码


第三题 hdu 1198 Farm Irrigation

点击打开hdu 1198

思路: 并查集
分析:
1 题目给定11快小方形,然后给定一个n*m的描述求n*m矩阵内的连通分量的个数
2 首先我们应该解决怎么保存11块小方形,我们可以利用一个思维的分量来描述,比如A我们描述成{1,0,0,1}
3 那么我们就可以做到在线进行并查集的操作,对于[i,j]这个方块,它可能和[i-1,j]和[i,j-1]进行相连,那么用i*m+j来唯一表示一个位置,那么最后枚举整个二维矩阵即可

点击打开查看代码


第四题 hdu 3635 Dragon Balls

点击打开hdu 3635
思路: 并查集
分析:
1 题目说有n个城市每一个城市有一个龙珠编号为i,现在有m行的输入包括两种的情况
T x y 把x所在的集合的所以龙珠转移到y集合上 Q x 询问x所在集合的龙珠的个数
2 我们利用rank[x]表示的是根节点为x的集合的元素的个数,但是现在我们发现求转移的次数不好求,刚开始我用的是一个vector数组来保存,比如v[x]表示以x为根节点的集合的元素,那么如果是把fx这个集合并到fy上的话,那么我们枚举v[fx]。但是这个方法TLE了
3 后来看了网上的题解,发现在求转移次数的时候我们也可以利用递归合并的思想,比如把fx所在的集合转移到fy的时候,那么我们只要把fx的转移次数加一,那么下次递归的时候我们在里面进行处理即可

点击查看代码


第五题 hdu 2473 Junk-Mail Filter

点击打开hdu 2473

思路: 并查集
分析:
1 题目初始化给定n个不同的点,然后给定m个操作,有两种类型 m x y 表示x和y是同一种类型,s x表示把x从集合中单独提前出来
2 这一题和uva11987很像,我们可以在初始化的时候把所有的节点的根节点设置成i+n, 那么我们遇到提取x的时候就不会碰到x刚好是根节点的情况
3 在合并x和y的时候我们应该要考虑的问题是x和y是不是之前被提前过的,如果都不是那么直接合并,否则我们应该注意合并的方向
4 遇到s x的时候我们把x的父亲节点设为cnt,cnt是一个移动的数值,注意这里cnt的值,数值应该要开大一点,这边我WA了很多次
5 最后统计连通分量的个数即可

点击打开查看代码


第六题 hdu 3172 Virtual Friends

点击打开hdu 3172

思路: 简单并查集
分析:
1 利用map对每个人进行编号,然后利用并查集即可
2 这一题有个地方就是输入case的时候要判断不等于EOF
点击打开查看代码


第七题 hdu 3047 Zjnu Stadium

点击打开hdu 3047

思路: 带权并查集
分析:
1 题目要求的是错误的条件的个数,这一题还是比较简单的带权并查集
2 我们用rank[x]表示的x到跟节点的距离,那么对于x和y来说,如果x和y在不同集合那么把x和y合并,否则直接判断rank[x] == (rank[y]+val)%300

点击查看代码


第八题 hdu 2818 Building Block

点击打开hdu 2818

思路: 带权并查集
分析:
1 题目给定2种指令 M x y把x的集合放在y集合的上面,C x求x的下面有多少个元素
2 我们用rank[x]表示x以下有多少个元素,那么对于指令M x y我们始终把左边的合并到右边,那么这样rank就满足压缩的性质
3 但是因为这边的合并和普通不一样,它是把x所在的集合放在y所在集合上面,实际上是x的跟节点合并到y集合的最远点,所以我们应该开个数组记录当前集合最远的点

点击查看代码


第九题 hdu 3461 Code Lock

点击打开hdu 3461

思路: 并查集+离散化+快速幂
分析:
1 题目给定长度为n的字符串,然后给定m个操作,询问最后的不同字符串的个数
2 考虑长度为n的时候,因为每个字符有26种情况('a'~'z'),所以有26^n。因为有m次的操作,题目中说了如果可以被变换那么认为是相同的字符串,那么不同的字符串就是所有不被操作区间的组合
3 那么我们利用并查集去求有操作的集合的个数,比如[1,3],[3,5]和[1,5]是三个集合,而[1,3],[4,5]和[1,5]则是2个集合
4 对于区间[l,r],那么我们一般转化为处理(l-1,r],这样不用考虑端点的问题了,最后利用快速幂求出ans即可

点击查看代码


第十题  hdu 1558 Segment set

点击打开hdu 1558

思路: 计算几何+并查集
分析:
1 有n个操作,最后求有几个集合或者说是连通分量
2 对于输入一条线段我们就去前面找能够和它相交的线段,利用并查集进行合并并且更新rank数组,rank[x]数组保存的是以x为跟节点的集合的线段的数量
3 这一题难点就是线段的相交判断

点击打开查看代码


【zoj】

第一题 zoj 3261 Connections in Galaxy War

点击zoj 3261

思路: 带权并查集
分析:
1 题目说的是有n个星球0~n-1,每个星球都有一个战斗值。n个星球之间有一些联系,并且n个星球之间会有互相伤害
2 根本没有思路的题,看了网上的思路才知道是逆向并查集。如果我们按照正常的并查集来做,以战斗值最大为根节点的话,当询问的时候很容易,但是碰到删除边的时候就很困难了,所以这里才用逆向的并查集思路
3 我们先把所有的输入保存,然后我们可以这么考虑,从后面往前面枚举q次条件,如果是destroy我们认为是加边,这样的话就很好维护并查集了
4 但是这边我们还要考虑初始的状态,由于涉及到删边而且不一定是删除所有的边,所以我们只要在m个关系里面扣除要删除的边,然后建立集合做为初始的状态

点击查看代码


【uva】

第一题 uva 1160 X-Plosives

思路: 普通并查集

分析:

1 题目意思不难理解,一些化学物品由两种元素组成,如果刚好有k个化学物品刚好由k个元素组成的话,那么将会爆炸

2 k个化学物品刚好由k个元素组成,那么等价于k条边刚好由k的点组成,那么这一题就变成判断是否在同一个集合的问题了

点击查看代码


第二题 uva 1329 Corporative Network

思路: 带权并查集

分析:

1  给定两种操作。I u v 是把节点u的父节点设为v ,并且节点u 和 节点v的节点距离为(|u-v|)%1000,E u询问u到跟节点之间的距离

2 比较简单的带权并查集

点击查看代码


第三题 uva 11987 Almost Union-Find

思路: 并查集
分析:
1 题目给定三种操作,符合并查集的模式
2 但是有一种操作和普通的并查集不同的是,2 p q要把p并到q的集合,那么这个时候p所在的集合就会发生变化,如果p刚好是它那个集合的跟节点那么这个时候就要重新调整这个集合
3 那么我们为了避免这种删除跟节点的情况出现,我们就把所有的i~n的节点的跟节点指向i+n,这样保证了删除的时候肯定不会是根节点。这样就变成了简单的并查集问题了

点击查看代码


第四题 uva  12232  Exclusive-OR

思路: 并查集的扩展应用
分析:
1 题目给定三种指令,I p v表示Xp = v, I p q v表示Xp^Xq = v,
Q k Xp1 Xp2...Xpk求Xp1^Xp2^...^Xpk的值。
2 对于的异或的性质:1 a^0 = a,2 a^c^b^c = a^b,异或一个数偶数次等于没有异或,因为异或偶数次的值为0,根据性质1那么结果没有影响
3 因此对于第一种命令I p v,我们可以虚拟出一个点Xn = 0,那么p^xn = v,那么第一和第二种命令我们可以统一成p^q = v的模式。
4 那么我们设val[i] = Xi^Xfather[i],但是要注意的是Xn要始终为那个集合的跟节点,因为这样我们才能够通过val[i]的值判断Xi是否存在。
5 那么Xp1^Xp2^...^Xpk = (val[Xp1]^val[Xp2]^...^val[Xpk])^(Xfather[xp1]^Xfather[xp2]^...^Xfather[xp2]);因为(val[Xp1]^val[Xp2]^...^val[Xpk])我们很容易求出来,所以我们现在就判断Xfather[xp1]^Xfather[xp2]^...^Xfather[xp2]是否存在,根据性质2我们只需要判断父亲节点出现次数为奇数的,如果父亲节点为Xn,那么值存在,否在不存在我们不能求出ans

点击查看代码




网友评论

登录后评论
0/500
评论
陈国林
+ 关注