type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
基础并查集
并查集就是用来维护一些元素之间的关系的集合。
例如 A的亲戚是B ，则我们可以把 A与B放到同一个集合中，表示AB属于同一种关系（亲戚关系），并且标记A和B的关系数组都为B
B的亲戚是C，则我们可以把 B和C也放到同一个集合中，则BC也属于同一个集合，并且标记B和C的关系数组都为C
再往后我们需要知道A和C是否是 同一个关系（即是否具有传递性），我们可以通过一直查找A和C的关系数组直到没有关系为止，看看他们是否是相同的元素值，即可知道他们是否属于同一个关系：
- A的关系数组的值是 B，而B的关系数组的值是C，所以A的关系为C
- C的关系数组的值就是C，所以A和C属于同一关系
- 并查集的初始化
每个元素的关系数组的关系只有其一个人：A默认为A，B默认为B
- 并查集的查找：（路径压缩）
每个元素在确定关系的时候都需要一直往上寻找，直到到达它的最顶级关系：A的关系不是B，而是往上B的关系，直到到达C，C的关系为其本身，这就到到达了A的最顶级关系，就是C
- 并查集的合并
合并是并查集最重要的功能，就如同上述的A和B或者B和C的确认关系的时候，把他们合并到同一个关系中，A的关系是B，B的关系为其本身
基础并查集便可以解决一系列的存在关系的问题
1. P1551 亲戚
这道题让我们判断两个人之间是否是亲戚，和我们上面的描述的基本是一致的，只需要判断他们两个是否属于同一个集合即可。
2. P1536 村村通
这道题其实就是求有多少个集合的问题。
如果一共有四个城市，有两条道路，分别为 1到3 和 3到4，则我们画图可以看出来 1 3 4 都属于同一个集合，2城市单独属于一个集合，总共有两个集合，因此如果要将两个集合合并，则需要添加的道路数量就是总集合数-1
种类并查集
种类并查集属于扩展域并查集一类。
不同的个体之间存在不同的关系，而每个相同个体之间都属于同一关系，不同的关系的个体的种类不同，因此就有了种类并查集。
1. P1892 [BOI2003]团伙
定义：
- 一个人的朋友的朋友是朋友
- 一个人的敌人的敌人是朋友
（很挺符合常理）
因此我们便可以确定两个并查集的种类：朋友和敌人。
不妨设每个人都有一个 enemies数组，表示他的敌人，则它的 enemies数组存储的可能是它的另一个敌人的朋友，即它的两个敌人互为朋友。
我们便可以确定出这样的关系：
- 如果A没有敌人：则A的敌人包括B和B的朋友们
- 如果A有敌人，则A的敌人是B的朋友
- 对于B同理
也可以使用这种并查集的做法：
表达敌人与朋友两种关系，不妨将并查集的数组开大两倍，作为并查集的扩展域，于是可以表达朋友以及敌人两部分，朋友对应第一倍，敌人对应第二倍。于是我们可以得到如下合并公式
- A和B是敌人的情况：
- A的敌人：A+n 是B 的朋友
- B的敌人： B+n是A 的朋友
- A和B是朋友： A和B
2. P1525 [NOIP2010 提高组] 关押罪犯
如题所示，我们需要把多个罪犯分成不同的种类，而每对罪犯之间又存在着不同的仇恨值。
我们需要把这些罪犯分到两个种类区域中，使得合并后每两个罪犯之间的最大仇恨值为一个理论最小值。
我们显然需要对每对罪犯仇恨值按照从大到小的顺序排序。
如果A和B 是敌人，则A和B要尽量分在两个不同的区域中，那么A不能和B在一起，要和谁在一起呢？
我们可以让A和（B的其他敌人）在一起，因为按照贪心的原理来看，如果A和B有仇，则A和B的仇人不一定有仇，相反B的仇人可能和A是朋友，因为他们都和B有仇，当然这句话是我的补充，题中并没有说他们是朋友，只是为了便于理解。
因此寻找B仇人们，让他们和A是一伙的；同理寻找A的仇人们，让他们和B是一伙的。因为是按照仇恨值从大到小排序的，因此A和B的仇人们一伙，如果存在敌对关系的话，仇恨值一定是比B要小的（A和B仇恨值大，先判断，越往后肯定仇恨值越小）；同理对于B和A的仇人们也是一样的。
一直把A和B的仇人们合并，B和A的仇人们合并。
在对A合并，寻找B的仇人的时候，直到B的仇人们的仇人的仇人.... 又回到了A，则A和B不可避免的又碰到了一起，即这个时候已经无法在分了，A和B不管找谁的仇人他们都是有仇的，则此时我们直接输出这个组合，此时这个组合关系的仇恨值一定是一个理论最小值，因为是按照从大到小排序的，既然不存在其他组合了，则这种一定是最小的。
3. P2024 [NOI2001] 食物链
我们在这个题中能得到三种关系：
- 属于同一类
- A吃B 的关系
- A被B吃 的关系
那么我们就可以创建三个种类，即三个集合，来分别合并他们之间的关系。
如果他们两个是同类的关系：输入1 u v
- u与v是同类（第一群系A）
- u+n和v+n是同类（第二群系B）
- u+n+n和v+n+n是同类（第三群系C）
如果它们两个是吃与被吃的关系： 输入 2 u v
由于他们三个群系属于一个环形生物链，并且同一群系中生物不能互吃
因此只能是 A群系吃B群系 ， B群系吃C群系， C群系吃A群系
我们如何判断话的真假？
- 如果输入2 u v，则uv一定不属于同一群系，因为uv存在u吃v的关系。
如果它是个假的：
- 只需要判断uv属于同一群系，则False
- 或者判断 v吃u ，则不满足 u吃v，则False
则这两种情况如下：
分别表示 uv 是同一群系 或者 u被v吃
- 如果输入 1 uv，则uv属于同一群系。
如果它是个假的：
- 只需要判断 存在 u吃v，则False；
- 或者判断 存在 v吃u，则False
则这两种情况如下：
完整代码如下：
带权并查集
就是在维护集合关系的树中添加边权的并查集，这样做可以维护更多的信息。
不难发现所谓的并查集本质上也是一种树，由于路径压缩的存在，使得一个并查集树中，其被压缩过的子节点总是直接指向根节点，于是我们可以给根节点与子节点之间的边进行赋权。
这个权值可以表示该节点与根节点之间的距离
待更新。。。。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/891eaff9-73e9-470a-9443-a3c4e2ef664f
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。