DFS递归必须用visited数组标记已访问节点以防无限递归；邻接表推荐vector；有向图判环需三色标记，遇color[v]==1才为真环。
DFS 递归实现必须处理访问标记
不加访问标记的 dfs 在无向图或有环图里会无限递归，直接栈溢出。C++ 没有运行时栈深检查，崩溃前往往只看到 std::stack_overflow 或静默终止。
- 用
vector<bool></bool>或unordered_set<int></int>记录已访问节点，索引即节点编号时优先选前者 - 标记必须在进入递归前设置（不是回溯后），否则同一节点可能被多次压栈
- 邻接表遍历时，如果图带重边，
visited能自然去重；但若逻辑上需区分“到达方式”，就得换用set<pair int>></pair>记录边访问状态
示例关键片段：
void dfs(int u) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) dfs(v);
}
}
用 stack 模拟递归时注意边遍历顺序
手动栈实现 DFS 和递归版行为不完全等价——主要差在邻接点的压栈顺序。递归天然按代码循环顺序深入，而 stack 是后进先出，反向压入才等效。
- 若要求和递归版完全一致（比如调试对比），遍历
graph[u]时得从尾到头压栈：for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) - 用
stack<pair int>></pair>存 {节点, 当前遍历到的邻接点下标} 可避免重复遍历整条邻接表，适合稀疏大图 -
stack版内存更可控，但每次push/pop有常数开销；对百万级节点，实测比递归慢 10%~15%
邻接表用 vector> 还是 vector>
- >
绝大多数情况直接用 vector<vector>></vector>。别被“链表插入快”误导——图建好后几乎不增删边，而 DFS 中的随机访问（如 graph[u][i]）在 vector 上是 O(1)，list 是 O(i)。
- 内存局部性：连续存储让 CPU 缓存命中率高，实测遍历速度提升 2~3 倍
- 初始化开销低：
vector<vector>>(n)</vector>比vector<list>>(n)</list>构造更快 - 只有当你需要频繁在邻接表中间插入/删除边（比如动态图算法），才考虑
list；但这时通常该换用vector<unordered_set>></unordered_set>
DFS 判环必须区分树边和回边
在有向图中，仅靠 visited 数组无法区分“回到祖先”和“回到已完结子树”。漏判会导致把 DAG 错认为有环。
立即学习“C++免费学习笔记（深入）”；
- 需要三色标记：
0=unvisited,1=visiting（在当前 DFS 栈中）,2=visited（已回溯完成） - 遇到
color[v] == 1才是真环；color[v] == 2是正常跨分支边 - 无向图可简化：只要
v不是父节点且已访问，就构成环——但要注意传父节点 ID 而非仅跳过上一个索引，否则多条边连同一对节点会误判
三色核心逻辑：
if (color[v] == 0) { dfs(v); }
else if (color[v] == 1) has_cycle = true;
实际写的时候，最容易卡在有向图环检测的三色状态管理上——少一个 color[u] = 2 的赋值，整个判环就失效，而且很难通过小样例发现。 
