write C++ code

Input: Number n of vertices (i.e. vertex set is {1,2, ,n}), and a list of edges (i,j) for 1 i,j n for a directed graph G. After this part, read a list of pair of vertices, one pair at a time.

Output: For each given pair of vertices i, j, output reachable if vertex j is reachable from vertex i via a directed path in G; not reachable, otherwise. Note that a directed path length can be larger than one.

Goal: Create the directed graph G from the given input, and decide for every given pair of vertices if the second vertex is reachable from the first vertex via a directed path in G. Assume that every vertex is reachable from itself in zero steps.

Hint: You can maintain an array of vertices in which you mark reachable vertices.

Example input file:

5

1 2

2 5

3 4

1 3

Example dialog (still during the same execution of the program):

Graph G is constructed

1 2

reachable

1 5

reachable

1 4

not reachable

2 4

not reachable

5 5 0

reachable

In this assignment, you write a C++ program for Problem A. Both correctness and efficiency of your programs are important. You are required to use ADJACENCY MATRIX to represent arcs of graph G. See a large input file for creating G on Page 5 (the last page). Test it with your list of pairs of vertices for reachable/not reachable queries.