#10711. 寻找图中是否存在路径

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

有一个具有 n个顶点的 无向图,其中每个顶点标记从 0 到 n - 1(包含 0 和 n - 1)。

图中有 m 条边,每条边用 [ui, vi] 表示顶点 ui 和顶点 vi 之间的边。 没有重复边,也没有到自身相连的边。

请你确定是否存在从顶点 s 开始,到顶点 t 结束的 有效路径 。

给你 n 和 m、m条边,以及 s 和 t,如果从 s 到 t 存在 有效路径 ,则返回 true,否则返回 false 。

输入格式

第一行:n 和 m,表示顶点数和边数

接下来 m 行,每条边连接的两个顶点

最后一行:开始顶点、结束顶点

输出格式

true,或,false

样例

输入1:

3 3
0 1
1 2
2 0
0 2

输出1:

true

解释:

存在由顶点 0 到顶点 2 的路径:

0 → 1 → 2

0 → 2

输入2:

6 5
0 1
0 2
3 5
5 4
4 3
0 5

输出2:

false

解释:

不存在由顶点 0 到顶点 5 的路径.

数据范围与提示

1 <= n <= 2 * 105

0 <= m <= 2 * 105

0 <= ui, vi <= n - 1, ui != vi

0 <= s, t <= n - 1

不存在指向顶点自身的边