DFS 深度优先搜索CSP-J

💡 核心思想

DFS 是一种遍历图或树的策略：从起点出发，沿一条路走到底，走不动了再回溯到上一个分叉点尝试其他路径。用递归实现最自然，也可以用栈实现。常用于连通性判断、路径搜索、全排列生成等。

🎯 直觉理解

DFS 就是"一条路走到黑"：从起点出发，能往前走就一直走，走不动了退回来换条路继续。就像走迷宫时沿着一面墙一直摸，最终能走遍整个迷宫。

实现上就是递归：进入一个点 → 标记已访问 → 递归所有未访问的邻居 → 回溯。可以做的事情很多：判断连通性、遍历所有方案、在树上统计。

关键是"标记"：忘记标记会死循环（两个点互相反复进入）。回溯类题目（如八皇后）还要在返回时撤销标记，两者别搞混——普通遍历只标记不撤销，搜索方案才需要恢复现场。

📝 算法流程

1. 标记当前节点已访问
2. 处理当前节点
3. 递归访问所有未访问的邻居
4. 回溯时如需搜索所有路径，取消标记

$$\text{时间复杂度：} O(V + E) \text{（每个顶点和边访问一次）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
vector g[100005];
bool vis[100005];
void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}
int main() {
    int n, m; cin >> 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); // 无向图
    }
    dfs(1);
    return 0;
}

⚠️ 常见坑点

📚 相关题目