最简DFS遍历用std::vector邻接表和递归实现，核心是visited数组防重访、递归访问未访邻点；图不连通时需遍历所有起点调用DFS。
用 std::vector 和递归写最简 DFS 遍历
标准 DFS 的核心是“走到不能走为止，再回退”。C++ 里用邻接表 + 递归最直观，不需要手动维护栈。关键点不是写得短，而是避免重复访问和栈溢出。
- 图用
std::vector<:vector>></:vector>存储，graph[u]是节点u的所有邻接点 - 必须用
std::vector<bool></bool>记录访问状态，不能靠节点值是否为 -1 或 0 来判断（数值可能合法） - 递归函数参数只需传当前节点
u，无需传父节点（无向图需额外处理环，但基础 DFS 不需要） - 如果图不连通，主逻辑要遍历所有未访问节点调用 DFS，不能只从 0 开始
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);
}
}
}
非递归 DFS 必须用 stack 模拟调用栈
递归 DFS 在深图上容易爆栈（比如链状图 1→2→3→…→10⁵），这时必须手写栈。注意：非递归版本的访问顺序和递归版一致，但“何时标记已访问”有坑。
- 错误做法：在
pop()后才设visited[u] = true→ 同一节点可能被多次压入栈 - 正确做法：在
push()前就标记visited[u] = true，确保每个节点只入栈一次 - 压栈顺序影响遍历路径（比如先压右子节点还是左子节点），但不影响连通性判断
- 用
std::stack<int></int>即可，不必存额外信息；若需记录深度或父节点，才扩展为struct
void dfs_iterative(int start, const vector<vector<int>>& graph, vector<bool>& visited) {
stack<int> st;
visited[start] = true;
st.push(start);
while (!st.empty()) {
int u = st.top(); st.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
st.push(v);
}
}
}
}
DFS 判环时无向图和有向图处理方式不同
单纯遍历不关心环，但做拓扑排序、强连通分量或检测图类型时，环检测是刚需。无向图和有向图的 DFS 环判定逻辑完全不同，混用会漏判或误判。
- 无向图：跳过「父节点」即可。递归时传
parent参数，遇到未访问邻居且不是父节点，就成环 - 有向图：必须用三色标记法（
unvisited/visiting/visited），仅靠visited数组无法区分跨分支边和回边 - 错误示例：对有向图只用二值
visited，把 A→B→C→A 里的 C→A 当成已访问而忽略，实际是环 - 三色法中，遇到
visiting状态的节点即存在环，此时可提前返回
用 DFS 求连通分量数量或最大连通块大小
这是 DFS 最常见的变体应用。核心不是改算法结构，而是调整「计数时机」和「作用域」。
立即学习“C++免费学习笔记（深入）”；
- 每次新进入未访问节点就启动一次 DFS，调用次数 = 连通分量数
- 在递归 DFS 内部用局部变量累加当前连通块大小，返回该值；主循环中取最大值
- 不要在全局变量里累加——多个连通块会互相污染
- 若图是带权的（如节点有权重），把累加对象换成权重和即可，逻辑不变
- 注意：节点编号不一定从 0 连续，要用
map<int bool></int>替代vector<bool></bool>，否则越界
