type
status
date
slug
summary
tags
category
icon
password
集合之中
能实现查询与合并的集合。
- 查询：判断两元素是否在同一集合中。
- 合并：将两个集合合并为一；
基础并查集
初始化：让每个元素（点）指向自己；
查询：找根节点（父节点），用来判断是否在同一集合；
合并：将两集合根节点合一；
路径压缩
当路径长度（链）较长时，为了在集合中更快查询根节点，将向根节点查询的步骤压缩：
按秩合并/启发式合并
当路径压缩后，会生成类似树的结构，需要简化树的结构，在合并时就应该将简单树向复杂树上合并。
- 用rank（秩）记录树的深度，初始化为一，将秩小的合并到秩大的上面。
扩展域
种类并查集
如果a和b是敌人，合并n+b和a，n+a和b
如果c和a是敌人，合并n+c和a，n+a和c
那么b和c就并在一起了
这样就符合了题目敌人的敌人是朋友的规则
食物链
加权并查集
使用情景：
- N个节点有$M$对关系($M$条边)，每对关系(每条边)都有一个权值$w$，可以表示距离或划分成多个集合时的集合编号，问题依然是判断是否有冲突或者有多少条边是假的(冲突)等。
思路：
- 给N个节点虚拟一个公共的根节点，增加一个数组$s[n]$记录每个节点到虚拟根节点的距离，把x,y直接的权值$w$看为$(x,y)$的相对距离。
- 时额外把$x，y$到虚拟根节点的距离($s$值)的相对差值设置为$w$；时，压缩路径的同时把当前$s$值加上之前父节点的$s$值，得到真实距离。
有关Notion安装或者使用上的问题，欢迎您在底部评论区留言，一起交流~
- Author:Grimner
- URL:https://tangly1024.com/article/example-6
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!