#495. 02 邻接表 DFS:有向图中的可达
题目描述
给定一张包含 个顶点和 条有向边的图,顶点编号为 。
已知两个顶点 ,请判断:能否从顶点 出发,沿着有向边走到顶点 ?
如果 ,则认为可以到达(不需要移动)。
本题用于练习 邻接表存图与 DFS(深度优先搜索)。由于数据规模较大,请避免直接使用 的邻接矩阵。
输入格式
第一行包含四个整数 ,表示顶点数、边数、起点、目标点。
接下来 行,每行两个整数 ,表示有一条从 指向 的有向边。
输出格式
如果可以从 到达 ,输出 Yes;否则输出 No。
请注意大小写。
样例 1
3 2 1 3
1 2
2 3
Yes
样例 2
3 2 1 3
1 2
2 1
No
样例解释
- 样例 1 中存在路径 ,因此可以到达。
- 样例 2 中,顶点 和 之间虽然可以往返,但无法到达顶点 。
数据范围与说明
- ;
- ;
- 输入可能包含重边和自环;
- 图是 有向图,不保证连通。
训练目标: 使用邻接表存图,借助 vis 标记已经访问的顶点,通过 DFS 判断目标顶点是否可达。由于最长路径可能很长,C++ 中建议优先使用显式栈实现的非递归 DFS,避免递归层数过深造成栈溢出。
手速前三短评
本题当前前三名可评论暂无短评