Description
Problem Description:
Given a Directed Graph and two vertices in it, write a Java program to check if
there is a path from the first given vertex to second. For example, in the following
graph, there is a path from vertex 1 to 3. As another example, there is no path
from 3 to 0. You can either use Breadth First Search (BFS) or Depth First Search
(DFS) to find a path between two vertices. Take the first vertex as source in BFS
(or DFS), follow the standard BFS (or DFS). If you see the second vertex in your
traversal, then return true. Else return false.
Input: The first line of input n indicates the number of vertices. The second line
of input m is the number of edges in the graph and the following m lines are the
directed edges in the graph. The next integer p is number of testing inputs and
the next p lines will be the test samples. The vertex numbers start from 0.
Output: The output consists of one line of p strings “YES” or “NO” indicating if
there is a path between the vertices or not. There is a single space between the
output strings.
Test Case Input Output
1 4
6
0 1
0 2
1 2
2 0
2 3
3 3
2
1 3
3 1
YES NO
