五合一网站做优化好用吗域名网站
并查集
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 | 通过 DFS |
| 721. 账户合并 | 维护账户到id的哈希表mail2id以及id到账户数组的哈希表id2mails，合并含有相同账户的id | 通过 |
| 1697. 检查边长度限制的路径是否存在 | 离线查询（询问全部给出，但是没必要按照询问的顺序处理，可以排序之后离线处理），注意自定义 sort 排序时最好加上引用& | 通过 |
| 2503. 矩阵查询可获得的最大分数 | 可以考虑点权或者边权（边权就考虑较大边），排序之后然后离线查询，询问排序下标就可以，可以看看灵神视频题解 | 边权 点权 |
| 1584. 连接所有点的最小费用 | Kruskal 算法：构造边，排序之后合并连通分量，维护分量长度和节点个数 | 通过 |
- 399. 除法求值
- 803. 打砖块
- 1202. 交换字符串中的元素
4. 参考
- 使用并查集处理不相交集合问题（Java、Python）
- 「手画图解」手写UnionFind，并查集 不再畏惧
- LC2503：两种写法：离线询问 + 并查集 / 最小堆（Python/Java/C++/Go）
- 总库：tryHard