DFS递归必须用visited标记防环，且需在递归前设true；迭代版用stack并倒序压入保序；判断环需区分无向图（传parent）和有向图（用recStack）；邻接表优选vector以提升缓存性能。
DFS 递归实现必须处理访问标记
不加访问标记的 DFS 在图中会无限循环，尤其遇到环或无向图边双向存在时。用 vector<bool> 或 unordered_set<int> 记录已访问节点是硬性要求。
-
visited[i] = true必须在进入递归前设置，不能放在递归调用之后 - 对邻接表
vector<vector<int>> graph，遍历graph[u]中每个v前先检查!visited[v] - 无向图中，即使边只存一次（如
u→v），v→u仍可能通过其他路径抵达，所以标记不可省
迭代版 DFS 要用 stack<int> 模拟调用栈
手动维护栈比递归更可控，适合防止爆栈或需记录路径/层数的场景。注意：栈中只存节点编号，不存边或状态标志。
- 入栈顺序影响遍历结果——若按邻接表原始顺序压栈，出栈是逆序；想保持左→右顺序，应倒序压入
- 每次
stack.pop()后立即设visited[u] = true，避免重复入栈 - 不要在循环内对当前节点的邻居反复 push/pop，应一次性遍历并过滤已访问节点
void dfs_iterative(int start, const vector<vector<int>>& graph) {
vector<bool> visited(graph.size(), false);
stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
stk.pop();
if (visited[u]) continue;
visited[u] = true;
// 处理节点 u：打印、存路径、更新状态等
// 倒序压入，保证邻接表顺序被保留（可选）
for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
if (!visited[*it]) {
stk.push(*it);
}
}
}
}
DFS 判断连通性与找环的逻辑差异
同一套 DFS 框架，仅靠参数和返回值设计就能区分用途。关键在如何定义“回边”和是否允许父节点干扰判断。
- 判断无向图是否有环：传入
parent参数，跳过v == parent的边；发现未访问却已入栈的邻居即为环 - 判断有向图环：需额外
recStack数组记录当前递归路径上的节点，而非仅visited - 连通分量计数：每启动一次未访问节点的 DFS，
components++，适用于非连通图
vector<vector<int>> 邻接表比 map<int, set<int>> 更快但不支持稀疏大编号
下标连续且范围已知（如节点编号 0~n−1）时，vector 是首选；若节点编号稀疏（如 1e9 级别 ID），必须用哈希结构，但 DFS 本身开销会上升。
立即学习“C++免费学习笔记（深入）”；
-
vector<vector<int>> graph(n)支持 O(1) 随机访问，push_back 平摊 O(1) - 用
map或unordered_map时，每次graph[u].count(v)是 O(log k) 或均摊 O(1)，但整体常数更大 - DFS 中反复调用
graph[u].size()和遍历，vector的 cache 局部性明显更好
recStack 的置位/复位时机——这些细节不写错，算法才能稳定输出正确结果。 
