3856: 图中是否存在路径

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：26 解决：9

题目描述

有一个具有 n 个顶点的双向图，其中每个顶点最多只能与另一个顶点相连（即没有重边，也没有自环）。
给定一个二维整数数组 edges，其中 edges[i] = [u, v] 表示顶点 u 和顶点 v 之间存在一条双向边。
请你判断：在该图中，是否存在从顶点 start 到顶点 end 的有效路径？
  • 如果存在路径，输出 YES。
  • 如果不存在路径，输出 NO。
注意：图可能是不连通的，也就是说可能存在孤立的顶点或独立的连通分量。

输入

  1. 第一行包含两个整数 n 和 m ，分别表示顶点的数量和边的数量。
  2. 第二行包含两个整数 start 和 end，分别表示起点和终点。
  3. 接下来 m 行，每行包含两个整数 u 和 v ，表示顶点 u 和 v 之间有一条双向边。

输出

输出一行字符串。如果存在从 start 到 end 的路径，输出 YES；否则输出 NO。

样例输入 复制 

3 1
0 2
0 1

样例输出 复制 

NO

来源/分类

提交提交记录统计露一手!