1. 引言
想象你在CSP-J赛场上，遇到一个迷宫问题：给定一张图，要求统计从起点出发能到达的所有节点数量。如果你暴力枚举所有路径，可能直接TLE；但如果学会深度优先搜索（DFS）加上记忆化搜索，就能轻松解决。这两种算法是CSP-J组必考的核心技巧，尤其适合处理树、图、状态转移等问题。今天咱们就彻底搞懂它们！
2. 核心概念讲解
DFS（深度优先搜索）
思想：像人走迷宫一样，一直往“深”走到底，发现死路再回溯。用栈或递归实现。
关键操作：
访问当前节点 -> 递归探索所有邻居 -> 回溯
记忆化搜索
- 思想：把重复计算的结果存起来，下次直接查表。比如爬楼梯问题，算过
dp[5]后，下次要dp[5]时直接返回，不用重新递归计算。
图示说明：
A -> B -> C (死路)
^ |
| D (新分支)
E (回溯到B)
3. C++代码示例
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; // 假设图有最多1000个节点
vector<int> g[N]; // 邻接表存储图
bool vis[N]; // 访问标记数组
// DFS函数：统计连通分量大小
int dfs(int u, int &size) {
vis[u] = true;
size++;
for (int v : g[u]) { // 遍历邻居
if (!vis[v]) {
dfs(v, size); // 递归深入
}
}
return size;
}
int main() {
int n, m; cin >> n >> m; // 读入n个节点m条边
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v), g[v].push_back(u); // 无向图建边
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
int cnt = 0; // 当前连通块大小
dfs(i, cnt);
ans += cnt; // 累加结果
}
}
cout << "连通分量总数: " << ans << endl;
return 0;
}
注释：
g[N]用邻接表存图，比邻接矩阵省空间。dfs的size参数通过引用传递，方便累加连通块大小。
4. 算法分析
| 特性 | DFS |
|—————|————————-|
| 时间复杂度 | O(V+E) |
| 空间复杂度 | O(V)（递归栈深度） |
| 适用场景 | 连通性/拓扑排序/树遍历 |
| 局限性 | 可能爆栈（可改非递归版）|
记忆化搜索优化：
- 将递归+重复计算改为
unordered_map缓存，例如爬楼梯问题：
unordered_map<int, int> memo;
int climbStairs(int n) {
if (n <= 2) return n;
if (memo.count(n)) return memo[n];
memo[n] = climbStairs(n-1) + climbStairs(n-2);
return memo[n];
}
5. 经典例题
洛谷P1027 [NOIP2018 普及组] 计数问题
题意：给定一棵树，求有多少种方案选k个节点构成子树（子树需连通）。
思路：树上动态规划 + DFS记忆化。定义
dp[u][s]表示以u为根的子树选s个节点的方案数，通过DFS遍历子树并合并状态。
6. 推荐练习
- 基础：洛谷P1164 [NOIP2012 提高组] 旅行家（DFS遍历岛屿）
- 进阶：洛谷P2965 [USACO] 奶牛体操（记忆化搜索优化DP）
- 综合：CF807D 最大子段和（DFS生成所有排列）
7. 小结
DFS+记忆化搜索是CSP-J组应对树/图问题的利器，核心在于“穷举+剪枝+缓存”。下期预告：背包问题与状态压缩DP，教你如何用二进制位高效处理物品组合！