图上的 DFS

一句话理解

图上的 DFS 沿着边走，访问所有能到的点。

为什么要学

判连通、建生成树、找环的底子。

讲解

邻接表存图。无向边两条有向边。从一点 DFS 能走到的就是它所在连通块。

例子

从 1 出发，沿着邻接表递归， vis 过的不再进。

常见错误

• 无向图忘了 vis，父子之间来回走。
• 邻接表下标从 0、点从 1 对不上。