树的 DFS 往下走不会回头，图不一样——图里有环（地铁环线），不记「去过哪」就会 1→2→4→3→1→2… 转圈转到天荒地老。图 DFS 的铁律：进每个节点前先看 vis 数组，去过就跳过，没去过就标记再进。
DFS = 走迷宫：从入口出发，选一条路一直走到头（走到死胡同、或者所有岔路都试过了），就回头到上一个岔口，换一条没试过的路继续走。树（比如组织架构图）没有环——往下走永远不会走回上面，不会迷路；但图有环（像地铁环线 1→2→4→3→1 绕一圈就回来了），不记「去过哪」，DFS 就会无限循环。所以图 DFS 多一条铁律：准备一个 vis 数组（bool，vis[i] = true 表示 i 去过）——进节点前查一下，去过就跳过，没去过就标上再进。这样每个节点恰好进一次，走完整张迷宫，所有能走到的节点都 visit 了。函数自己调自己 = 递归，「走到头回头」正是递归返回时干的。
// 树（无环）：往下走不会走回上面 // 1 // / \ // 2 3 // /\ // 4 5 // DFS(1) → DFS(2) → DFS(4) → 回头 → DFS(5) → 回头 → DFS(3) → 完 // 每个节点只有一个「来路」，递归返回时自然回头，不会撞见老朋友 // // 图（有环）：地铁环线，会走回起点 // 1 ── 2 // │ │ // 3 ── 4 // 没有 vis 时：DFS(1) → 2 → 4 → 3 → 又见 1 → 又见 2 → 又见 4 → … // 无限循环！（递归版：栈越叠越厚 → 栈溢出 / 超时） // // 解法：vis 数组（bool，初始全 false） // 进节点前：if (vis[i]) 跳过；否则 vis[i] = true 再进 // 效果：每个节点恰好进一次，环被 vis「剪断」
// 图：边 1-2、1-3、2-4、3-4、4-5、5-6 // adj[1]={2,3} adj[2]={1,4} adj[3]={1,4} adj[4]={2,3,5} adj[5]={4,6} adj[6]={5} // // 从 1 出发 DFS（邻居从小到大试）： // 第 1 步：进 1，vis[1]=1，顺序：1 // 第 2 步：试 1 的邻居 2（未去）→ 进 2，vis[2]=1，顺序：1 2 // 第 3 步：试 2 的邻居 1（已去，跳过）→ 4（未去）→ 进 4，vis[4]=1，顺序：1 2 4 // 第 4 步：试 4 的邻居 2（已去）→ 3（未去）→ 进 3，vis[3]=1，顺序：1 2 4 3 // 第 5 步：试 3 的邻居 1（已去）→ 4（已去）→ 没路了，回头到 4 // 第 6 步：4 的下一个邻居 5（未去）→ 进 5，vis[5]=1，顺序：1 2 4 3 5 // 第 7 步：试 5 的邻居 4（已去）→ 6（未去）→ 进 6，vis[6]=1，顺序：1 2 4 3 5 6 // 第 8 步：6 的邻居 5（已去）→ 回头 → 一路回头 → 完！ // // 最终访问顺序：1 2 4 3 5 6（6 个节点各进恰好 1 次） // 关键：1 的邻居 3 为什么没从 1 进？——2→4→3 这条路上 3 已经被访问， // 回到 1 再试 3 时 vis[3]=1 → 跳过（这条 1—3 边就是「回头路」）
// 图：n = 6，边只有 1-2、3-4（5、6 是孤点） // // 思路：外层 for 从 1 数到 n，每次发现「没访问过的节点」 // = 一个新孤岛的入口 → cnt++，然后 DFS 把整个岛标记掉 // // i = 1：vis[1] 未访问 → cnt = 1 → DFS(1)：访问 {1, 2} // i = 2：已访问，跳过（同属 1 号岛） // i = 3：未访问 → cnt = 2 → DFS(3)：访问 {3, 4} // i = 4：已访问，跳过 // i = 5：未访问 → cnt = 3 → DFS(5)：访问 {5} // i = 6：未访问 → cnt = 4 → DFS(6)：访问 {6} // 答案：4 个连通块 = {1,2}、{3,4}、{5}、{6} // // 森林（无环图）公式：连通块 = n − 边数 k // 本例：6 − 2 = 4 ✓（每个连通块是一棵树：t 个节点的树恰有 t−1 条边， // 加起来：边数 = Σ(t_i − 1) = n − 连通块数）
// 无向图（子任务 2 的 6 节点图）：s = 1, t = 6 // DFS(1) 访问 {1,2,4,3,5,6} → vis[6] = true → 1 能走到 6 ✓ // 无向图：能走到 ⇔ 能走回（同在一个连通块里） // // 有向图：n = 6，边 1→2、2→3、3→1、5→6 // DFS(1)：访问 {1, 2, 3}（3→1 回头路，vis 挡住）→ vis[6] = false // → 1 到不了 6（6 只能从 5 进，1 到不了 5） // DFS(6)：访问 {6}（6 没有出边）→ vis[1] = false → 6 也到不了 1 // 有向图：s 能到 t ≠ t 能到 s（方向！）
// 题目：读入 n 个节点 m 条无向边的图，然后： // ① 输出连通块（孤岛）个数； // ② 读入 s t，判断 s 能不能走到 t，输出 YES / NO。 // 输入：第 1 行 n m；接下来 m 行每行 u v（无向边）；最后 1 行 s t。 #include <iostream> #include <vector> #include <cstring> using namespace std; const int N = 100005; vector<int> adj[N]; // 邻接表 bool vis[N]; // 去过没？ int n, m; void dfs(int u) { // 从 u 出发，访问所有能走到的节点 vis[u] = true; // 先标记再扩展（环里才不会打转） for (int i = 0; i < (int)adj[u].size(); i++) { int v = adj[u][i]; if (!vis[v]) dfs(v); // 只递归「没去过」的邻居 } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } // ① 连通块计数：每遇到一个没访问过的节点 = 一座新孤岛 int cnt = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) { cnt++; dfs(i); } } cout << cnt << endl; // ② 通路判断：从 s 做一次 DFS，看 vis[t] memset(vis, 0, sizeof vis); // 重置 vis int s, t; cin >> s >> t; dfs(s); cout << (vis[t] ? "YES" : "NO") << endl; return 0; } // 样例：n=6, m=6；边：1 2 / 1 3 / 2 4 / 3 4 / 4 5 / 5 6；查询：1 6 // 输出：1（全图一座岛）/ YES（1 能到 6，路径如 1→2→4→5→6）