Challenge 09: Graph Paths

Problem

Given a directed graph, determine if there is a path between two nodes in the graph.

For instance, in Graph 4 above, there is a path from A to D, but no path from D to A.

You will be given a series of graphs specified by edge pairs, and then a series of paths to check for. For each path, you are to determine if the graph contains a route from the specified source to the specified destination.

Input

You will be given a series of directed graphs from standard input in the following format:

NEDGES
SRC1 DST1
...
NPATHS
SRC1 DST1
...

The first line specifies the number of edges in the directed graph, followed by NEDGES pairs of nodes where the first string is the source and the second string is the destination, which indicates that there is an edge from source to destination. After this, you are given NPATHS which is the number of paths or routes to search for. The exact paths to verify follow this line as a a series of source and destination pairs.

Output

For each path for a particular directed graph, output a statement saying:

In Graph 1 there is a path from A to B

if there is a path from A to B. Otherwise, output a statement saying:

In Graph 1 there is no path from A to B

Put an empty line between the output for each graph as shown below.

Example

Given the following input:

1
A B
2
A B
B A

3
A B
A C
B C
4
A B
A C
B C
C B

Your program should output the following:

In Graph 1 there is a path from A to B
In Graph 1 there is no path from B to A

In Graph 2 there is a path from A to B
In Graph 2 there is a path from A to C
In Graph 2 there is a path from B to C
In Graph 2 there is no path from C to B

Requirements

Your solution must meet the following requirements:

1. You must represent the graph using either adjacency list or adjacency matrix.

Hints

1. You should perform some sort of traversal such as depth-first search or breadth-first search.

2. You can use a std::map or std::unordered_map to represent the directed graph.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Challenge 09 - TA assignment list.

$ cd path/to/repo                   # Go to your repository
$ git checkout master               # Make sure we are on master branch
$ git pull                          # Make sure we have changes for GitLab
$ git pull upstream master          # Fetch and merge upstream changes
$ git checkout -b challenge09       # Create challenge09 branch
...                                 # Do your work
$ git commit                        # Commit your work (can do this multiple times)
$ git push -u origin challenge09    # Push branch to GitLab