DFS 模板

一句话理解

DFS 模板：标记、遍历邻居、必要时回溯。

为什么要学

先背清再改。

讲解

void dfs(u){ vis[u]=1; for v in g[u]: if !vis[v] dfs(v); }

需要恢复的场合 vis 要改回 0，那是回溯搜索。

例子

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) if (!vis[v]) dfs(v);
}

连通块式 DFS，标记不撤销。

常见错误

• 图有向、无向混用。
• 递归深度过大爆栈，改成显式栈。