用显式栈替代递归DFS可避免栈溢出：压入{节点, 下一邻接点索引}，用引用传图，配合访问标记数组；递归版需限制深度或增大栈空间。
dfs 函数怎么写才不会栈溢出
递归实现 dfs 最常见，但图太大或深度太深时，std::stack 溢出或系统栈爆掉是真实问题。C++ 默认栈空间通常只有 1–8MB，深达 10⁵ 层的递归基本必崩。
- 用显式栈（
std::stack）替代递归：把「当前节点」和「下一步要访问的邻接点索引」一起压栈，避免函数调用开销和栈帧累积 - 避免在
dfs参数里传图（如vector<vector>> graph</vector>），改用引用或全局/类成员变量，否则每次递归都拷贝邻接表 - 如果必须递归，编译时加
-Wstack-protector检查，运行前用ulimit -s unlimited（仅限 Linux 本地调试，不解决本质问题）
示例片段（迭代版）：
stack<pair<int, int>> stk; // {node, next_index}
stk.push({start, 0});
vector<bool> vis(n, false);
vis[start] = true;
while (!stk.empty()) {
auto [u, i] = stk.top();
if (i < graph[u].size()) {
int v = graph[u][i];
stk.pop();
stk.push({u, i + 1});
if (!vis[v]) {
vis[v] = true;
stk.push({v, 0});
}
} else {
stk.pop();
}
}
邻接表用 vector 还是 list 存
vector<vector>></vector> 是绝大多数场景的正确选择，别被“链表插入快”误导——DFS 遍历邻接点是顺序读取，vector 的 cache 局部性碾压 list。
-
vector支持 O(1) 随机访问下标i，迭代邻接点时 CPU 能预取；list每次next都是随机内存跳转，实际慢 2–5 倍 - 建图阶段若频繁增删边（比如动态图），才考虑
vector+ 标记删除，或用unordered_set；普通练习题完全不需要 - 注意 reserve：建图前对每个
graph[u]调用reserve(deg[u])，避免多次 realloc
visited 数组用 bool 还是 int
用 vector<bool></bool> 有陷阱，它不是真正的容器，而是位压缩特化类型，operator[] 返回代理对象，不能取地址、不能用于某些算法（比如 fill 或绑定到引用）。实际中更推荐 vector<char></char>。
-
vector<char></char>占 1 字节/元素，内存和vector<bool></bool>一样，但行为标准、可调试、支持所有 STL 算法 - 如果需要多状态（比如未访问 / 正在递归栈中 / 已完成），就用
vector<int></int>，值为 0/1/2，别硬套bool - 全局图 DFS 中，
visited必须重置：每次新查询前fill(vis.begin(), vis.end(), 0)或直接构造新 vector
无向图 DFS 怎么避免回到父节点
最简方案是传入父节点 id，在遍历时跳过——这比检查边是否已访问更轻量，也避免了 visited 数组误判（比如两点间多条边）。
立即学习“C++免费学习笔记（深入）”；
- 递归写法：参数加
int parent，循环中if (v == parent) continue; - 迭代写法：栈元素扩展为
{node, parent, next_index}，压栈子节点时传入当前 node 作为其 parent - 别用 “只走未访问节点” 来防回退：在无向图中，
v已访问 ≠v是父节点，可能只是另一条路径先抵达，这样会漏边
复杂点在于：树和图的边界模糊时（比如基环树），单靠父节点过滤不够，得结合时间戳或环检测逻辑。但纯连通性/遍历题，父节点过滤足够且最稳。
