递归版dfs必须在递归调用前标记visited[u]=true，否则在无向图或含环有向图中会无限循环或重复访问；visited[i]表示节点i是否已进入当前dfs树。
递归版 DFS 为什么必须用 visited 数组标记访问状态
不标记会导致无限循环或重复访问——尤其在无向图或含环有向图中。visited[i] 表示节点 i 是否已被递归进入过（不是“刚被访问”，而是“当前 DFS 树中已存在”）。常见错误是只在打印/处理时设标记，而应在递归调用前就设：
void dfs(int u) {
visited[u] = true; // ✅ 必须在此处标记
cout << u << " ";
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v); // ❌ 若这里才标记，v 可能被多个邻居重复压入栈
}
}
}若图用邻接表 vector<vector>></vector> 存储，节点编号从 0 开始，visited 大小需与节点数一致。
非递归 DFS 用 stack 实现时，入栈和出栈顺序决定遍历路径
标准非递归 DFS 应模拟递归的“深度优先”行为：每次取栈顶，立即标记为已访问，并将所有未访问邻接点压栈。关键点：
- 压栈顺序影响结果：若邻接表是
{1,2,3}，先压3再压2最后压1，则出栈顺序为1→2→3（即按原顺序遍历） - 不能在出栈时才标记——否则同一节点可能被多次压入；必须在压栈前检查
!visited[v]，且压栈即标记 - 不推荐用
stack<pair bool>></pair>模拟“是否回溯”，那属于 DFS 迭代器写法，不是基础遍历需求
stack<int> st;
st.push(start);
visited[start] = true;
while (!st.empty()) {
int u = st.top(); st.pop();
cout << u << " ";
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true; // ✅ 压栈前标记
st.push(v);
}
}
}
邻接矩阵 vs 邻接表对 DFS 时间复杂度的影响
使用邻接矩阵（vector<vector>></vector>）时，每次遍历节点 u 都要扫描整行（O(V)），总时间是 O(V²)；邻接表只遍历实际边，总时间是 O(V + E)。实际项目中除非图极稠密或节点数
vector<vector>></vector> 是主流邻接表，但若频繁删边，可考虑 vector<set>></set>；不过 DFS 不涉及删边，无需过度设计graph[u].size() 写成 n）会导致越界或漏边递归太深导致栈溢出？std::stack 非递归版也不是万能解药
当图节点数超 10⁵ 且深度极大（如链状图），递归 DFS 很容易触发栈溢出；此时非递归版确实能避免函数调用栈问题。但要注意：
-
std::stack默认用deque实现，内存分配较频繁；对超大图，可换用stack<int vector>></int>提升连续内存局部性 - 非递归版仍需
O(V)空间存visited和stack，空间复杂度没变，只是把栈空间从系统栈挪到了堆上 - 若需获取路径、回溯状态（如找连通分量中的割点），单纯非递归 DFS 不够，得补全“当前层数”或“父节点”信息，这时递归结构反而更直观
vector::begin()/end() 或未 reserve 容量——这些细节比选递归/非递归更影响实测表现。 
