CJDF01｜道路是否可达 题解

核心算法

从 $s$ 开始进行深度优先搜索，用 visited 记录已经到达的地点。

思路推导

从当前地点 $u$ 枚举所有 $a_{u,v}=1$ 的地点 $v$。若 $v$ 尚未访问，就继续从 $v$ 搜索。到达 $t$ 时即可确认答案。

正确性说明

DFS 会沿每条从 $s$ 出发且尚未访问的道路继续搜索，因此所有从 $s$ 可达的地点最终都会被访问；不可达地点不会被错误访问。故 visited[t] 与“$s$ 能到达 $t$”等价。

复杂度

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$（不计输入矩阵）。

易错点

• 道路有方向，不能自动把 $a_{i,j}$ 当作 $a_{j,i}$；
• 进入结点后立刻标记，避免环导致无限递归；
• $s=t$ 时答案应为 YES。