dfs在c++中需靠显式状态控制，邻接表递归必须传节点索引并用引用visited防重入；手动栈需压栈前标记访问；树可省visited，图必须用；慎用vector。
DFS 在 C++ 中不是靠“教程逻辑”驱动的，而是靠明确的状态控制和递归终止条件；写错往往是因为没管住访问标记或忽略图的存储结构差异。
用 vector<vector>></vector> 存邻接表时怎么写 DFS 递归
这是最常用也最容易出错的场景：邻接表本身不带节点 ID，递归函数必须显式传入当前节点索引，并用外部 visited 数组防重入。
-
visited必须是全局或引用传入，不能在每次递归里新建 - 遍历邻居要写成
for (int neighbor : graph[u])，别手抖写成for (int i = 0; i - 递归前必须先设
visited[u] = true，否则可能重复进入同一节点
void dfs(int u, const vector<vector<int>>& graph, vector<bool>& visited) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v, graph, visited);
}
}
}
遇到 std::stack<int></int> 手动模拟栈时要注意什么
递归本质是系统栈，手动栈容易漏掉“已访问但未处理完”的状态。非递归 DFS 不等于把递归改成 while + stack 就完事。
- 压栈前就要标记
visited[u] = true，否则同一节点可能被多次压入 - 出栈后才处理该节点（比如输出、收集），但邻居的访问判断仍依赖
visited - 如果要还原路径或记录深度，得额外存
pair<int int></int>（节点+深度），不能只压节点
DFS 遍历树和遍历一般图的区别在哪
树无环、有向且连通，所以不需要 visited 数组也能跑通；但只要图里存在环或多个连通分量，不加访问控制就会无限递归或漏节点。
