网站设计 专业,wordpress 媒体库清理,wordpress中文安装教程视频教程,网站维护细则并查集
1. 概念 并查集主要用于解决一些 元素分组 问题#xff0c;通过以下操作管理一系列不相交的集合#xff1a;
合并#xff08;Union#xff09;#xff1a;把两个不相交的集合合并成一个集合
查询#xff08;Find#xff09;#xff1a;查询两个元素是否在同一…并查集
1. 概念 并查集主要用于解决一些 元素分组 问题通过以下操作管理一系列不相交的集合
合并Union把两个不相交的集合合并成一个集合
查询Find查询两个元素是否在同一个集合中具体实现方面使用一个数组 parent 存储每个变量的 父节点信息每个节点的连通分量信息其中的每个元 素表示当前变量所在的连通分量的父节点信息如果父节点是自身说明该变量为所在连通分量的根节点。初始化时 所有变量的父节点都是它们自身 2. 解题技巧我的总结 1 合并集合两个集合有相似的性质合并二者以前一个集合的索引作为根。 性质map为空 对每个集合m, 索引i{ 如果 m的性质 在 性质map 中 存在, 根为preIdx{ i 加入 preIdx }否则{ 性质map添加新健值对 (m性质, i) } } 题目说明实现947. 移除最多的同行或同列石头相同性质为两个集合拥有相同的行号或列号用一个map记录每个行号、列号第一次出现的位置我的提交721. 账户合并相同性质为两个集合拥有相同的元素用一个map记录每个元素第一次出现的位置我的提交1722. 执行交换操作后的最小汉明距离AB交换、BC交换、…EF交换 - A、B、C、…、F可以任意交换我的提交
3. 更多练习
基础
题目说明答案990. 等式方程的可满足性先将全部合并其次找出!的根节点如果一样则不行通过547. 省份数量简单的并查集维护连通分量个数也可以 DFS 和 BFS通过
进阶
题目说明答案959. 由斜杠划分区域重点在将斜杠怎样拆分成单元格外部添加成3*3还可以DFS内部分解成4*4通过 DFS721. 账户合并维护账户到id的哈希表mail2id以及id到账户数组的哈希表id2mails合并含有相同账户的id通过1697. 检查边长度限制的路径是否存在离线查询询问全部给出但是没必要按照询问的顺序处理可以排序之后离线处理注意自定义 sort 排序时最好加上引用通过2503. 矩阵查询可获得的最大分数可以考虑点权或者边权边权就考虑较大边排序之后然后离线查询询问排序下标就可以可以看看灵神视频题解边权 点权1584. 连接所有点的最小费用Kruskal 算法构造边排序之后合并连通分量维护分量长度和节点个数通过 399. 除法求值 803. 打砖块 1202. 交换字符串中的元素
4. 参考
使用并查集处理不相交集合问题Java、Python「手画图解」手写UnionFind并查集 不再畏惧LC2503两种写法离线询问 并查集 / 最小堆Python/Java/C/Go总库tryHard
