DFS算法的学习

DFS

一. 介绍

深度优先遍历

二. 模板

/** @description 深度优先遍历* @param: p 邻接表* @param: vis 记录访问过的位置* @param: i 当前正在访问的位置* @returns int* @author yamu* @date 2025/5/9 14:17*/
public void dfs(List<Integer>[] p, boolean[] vis, int i) {vis[i] = true;for (int j : p[i]) {if (!vis[j]) {//操作dfs(p, vis, j);}}
}

三.题单

参考灵神题单

1. 547. 省份数量 - 力扣（LeetCode）
2. 1971. 寻找图中是否存在路径 - 力扣（LeetCode）
3. 797. 所有可能的路径 - 力扣（LeetCode）
4. 841. 钥匙和房间 - 力扣（LeetCode）
5. 2316. 统计无向图中无法互相到达点对数 - 力扣（LeetCode）
6. 1319. 连通网络的操作次数 - 力扣（LeetCode）
7. 2192. 有向无环图中一个节点的所有祖先 - 力扣（LeetCode）
8. 3387. 两天自由外汇交易后的最大货币数 - 力扣（LeetCode）
9. 2101. 引爆最多的炸弹 - 力扣（LeetCode）
10. 721. 账户合并 - 力扣（LeetCode）
11. 924. 尽量减少恶意软件的传播 - 力扣（LeetCode）
12. 3108. 带权图里旅途的最小代价 - 力扣（LeetCode）

547 模板题
1971 模板题
797 模板题
841 模板题
2316 模板题
1319 模板题，需要对点集的点数和边数进行计算
2192 模板题，好题，需要统计到达某个节点可行路径上的所有点，dfs勉强能过
3387 好题，建图之后dfs或bfs
2101 好题，dfs求连通集的最大点数
721 究极好题，程序上处理多对多的关系，并且合并
924 究极好题，需要统计每个点的唯一来源
3108 好题，dfs实现连通集