邻接表用vector构建，外层索引为顶点编号，内层存邻居；无向图双向加边，有向图单向加边；dfs递归需含当前节点、visited数组和邻接表，缺visited将导致无限递归。
邻接表怎么建：用 vector<vector>></vector> 最直接
图的邻接表本质是每个节点维护一个邻居列表。C++ 中最常用、最轻量的方式是 vector<vector>></vector>，外层索引代表顶点编号（0-based 或 1-based），内层 vector 存所有邻接点。
注意点：
- 如果顶点数已知（比如
n个），初始化时就预留空间：vector<vector>> graph(n);</vector> - 无向图要双向加边：
graph[u].push_back(v); graph[v].push_back(u); - 有向图只加单向：
graph[u].push_back(v); - 避免重复建边（除非题目允许重边），否则 DFS 可能误入环或多次访问同一节点
DFS 递归函数怎么写：三个核心要素缺一不可
标准 DFS 递归实现必须包含：当前节点、访问标记数组、邻接表。漏掉 visited 就会无限递归（尤其在有环图中）。
void dfs(int u, vector<bool>& visited, const vector<vector<int>>& graph) {
visited[u] = true;
// 处理当前节点（如输出、计数、存路径等）
cout << u << " ";
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v, visited, graph);
}
}
}
常见错误：
立即学习“C++免费学习笔记（深入）”；
- 忘记传
visited引用，导致每次递归都是副本，标记无效 - 把
visited声明在函数内部，每次调用都重置 - 没检查
v是否越界（尤其当邻接表里存了非法索引时）
从哪个点开始遍历：别默认只跑 dfs(0)
图不一定是连通的。只调用一次 dfs(0) 只能访问到 0 所在的连通分量。要遍历全图，必须对每个未访问节点启动 DFS：
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(i, visited, graph);
// 这里可加换行或分隔符，表示一个新连通分量
cout << "\n";
}
}
典型场景：
- 求连通分量个数 → 统计外层循环中进入
dfs的次数 - 判断图是否连通 → 看最终
visited是否全为true - 重建森林结构 → 每次进入
dfs对应一棵生成树的根
想记录路径或回溯怎么办：加参数 + 回退操作
如果需要输出某条从起点到终点的路径，或做路径相关决策（如找最短路、判断是否存在某约束路径），就得把当前路径存下来，并在递归返回时弹出栈顶：
void dfs_path(int u, int target, vector<bool>& visited,
vector<int>& path, const vector<vector<int>>& graph) {
visited[u] = true;
path.push_back(u);
if (u == target) {
// 找到目标，可打印或保存 path
for (int x : path) cout << x << " ";
cout << "\n";
} else {
for (int v : graph[u]) {
if (!visited[v]) {
dfs_path(v, target, visited, path, graph);
}
}
}
path.pop_back(); // 关键：回溯，恢复现场
visited[u] = false; // 若允许多次经过同一节点（如带权图枚举所有路径），需取消注释
}
容易被忽略的细节：
-
path.pop_back()必须放在递归调用之后、函数返回之前，否则路径残留 - 若题目不允许重复访问节点（大多数 DFS 遍历题），
visited[u] = false不该恢复；只有明确要求“路径可重用节点”时才放开 - 路径过长时，
vector<int>& path</int>传引用避免拷贝开销
