11.20

bfs–spfa—distra

需要遍历节点的三种考虑 dfs 并查集 bfs
洪水填充，计算连通块类 dfs 代码短 有优势

并查集适合解决有 一类共同性质的集合的拼接
稍微进阶一点的就是 并查集的标记 维护距离并查集 维护size并查集 并查集的撤销处理

并查集在网格图的处理（可以用x*col+y计算唯一点 或者用降维数组
row[66]=1 col[33]=1 表示1号点（66,33） 如果遇到有行或者列相关的 点 直接和1号点合并
当行和列都比较大时候
947. 移除最多的同行或同列石头
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/description/）

区间并查集 怎么把边合并转换成点合并的思路
3244. 新增道路查询后的最短距离 II

https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-ii/description/

既可以用可撤销并查集 也可已用dfs 的题目 本质是连通块
2092. 找出知晓秘密的所有专家
https://leetcode.cn/problems/find-all-people-with-secret/

dfs
这东西很万能，小到网格图最短路，大到各种奇奇怪怪的回溯搜索都可以解决
两个模版
一个是在进入递归函数前进行边界处理， 可以统计相邻格子信息
另一个在递归函数一开始进行边界处理 只统计自己的信息

bfs
注意st数组 只要在队里 就表示遍历过 就要改st
记住 先判断st 然后马上标记为true 再入队。

spfa
前置处理 初始化dist 以及0点 初始化h
把0点入队列
取出队列，st设false
遍历其他点 都进行松弛操作
如果成功操作，如果这个点不在队列，入队，st标记

distra
前置处理 初始化dist 以及0点 初始化h
n-1次循环 每次确定一个点
找到最近距离点t，保证t此时未被确定
确定t。
用t去更新相邻点。

堆优化
前置处理 初始化dist 以及0点 初始化h
0,0入堆
每次拿到一个最近点
如果已经确定 continue
确定t
用t去更新相邻点。
如果成功操作， 入堆

st数组汇总
• bfs算法表示的是否被遍历过
• dijistra表示的是是否在确定集合中
*spfa表示当前点是否在队列内

熟悉邻接表

探究t 以及什么时候应该用结构体。
t每一次是起点 可以获得t的抵达点j /e[i]以及这段路程的信息w[i]
需要记录上一次t作为终点的路径信息。用结构体记录
经典例题
https://leetcode.cn/problems/shortest-path-with-alternating-colors/submissions/581673898/