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

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

题目描述

有一个具有 n个顶点的 双向 图,其中每个顶点标记从 0 到 n - 1(包含 0 和 n - 1)。图中的边用一个二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。

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

给你数组 edges 和整数 n、start和end,如果从 start 到 end 存在 有效路径 ,则返回 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 <= edges.length <= 2 * 105

edges[i].length == 2

0 <= ui, vi <= n - 1

ui != vi

0 <= start, end <= n - 1

不存在双向边

不存在指向顶点自身的边