并查集专题【完结】

个人整理 并查集

【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 根据题目的意思，空树也是树或者只有一个跟节点的是树

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 1160X-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

点击查看代码