1405 - 寻找图中是否存在路径
Time Limit : 1 秒
Memory Limit : 128 MB
有一个具有 n
个顶点的 双向 图,其中每个顶点标记从 0
到 n - 1
(包含 0
和 n - 1
)。图中的边用一个二维整数数组 edges
表示,其中 edges[i] = [u_i, v_i]
表示顶点 u_i
和顶点 v_i
之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 source
开始,到顶点 destination
结束的 有效路径 。
给你数组 edges
和整数 n
、source
和 destination
,如果从 source
到 destination
存在 有效路径 ,则输出 true
,否则输出 false
。
Input
第一行为一个整数n,表示edges
数组的长度
以下n行,每行2个整数,分别表示每条边的顶点
第n+2行为2个整数,分别表示source
和destination
Output
如果从 source
到 destination
存在 有效路径 ,则输出 true
,否则输出 false
Examples
Input
3 0 1 1 2 2 0 0 2
Output
true
Input
5 0 1 0 2 3 5 5 4 4 3 0 5
Output
false
Hint
1 <= n <= 2 * 10^5
0 <= edges.length <= 2 * 10^5
edges[i].length == 2
0 <= u_i, u_i <= n - 1
u_i != v_i
0 <= source, destination <= n - 1
不存在重复边
不存在指向顶点自身的边