Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and a list of edges
ID: 3669651 • Letter: I
Question
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 ivia a directed path in G; “not reachable”, otherwise. Note that a directed path lengthcan 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<ENTER>
reachable
1 5 <ENTER>
reachable
1 4 <ENTER>
not reachable
2 4 <ENTER>
not reachable
5 5 0 <ENTER>
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.
Explanation / Answer
==============File name chegg.cpp======================
#include <iostream>
using namespace std;
#define N 20
#define row 10
#define col 10
int main()
{
int nodes, source, dest;
int adjMatrix[row][col];
cout<<"Enter number of nodes: ";
cin>>nodes;
//initial we are setting 0 to all nodes
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
adjMatrix[i][j]=0;
//inserting 1 for particular node
for (int i = 0; i < nodes; i++)
{
cout<<"Please Enter edge";
// vertices value should not greater then row number or column number
cin>>source>>dest;
adjMatrix[source-1][dest-1]=1;
adjMatrix[source-1][source-1]=1;//self reachable node
adjMatrix[dest-1][dest-1]=1;//self reachable node
}
char c;
while(1){
cout<<"please enter the node to be search ";
cin>>source>>dest;
if(adjMatrix[source-1][dest-1]==1)
cout<<"reachable ";
else
cout<<"not reachable ";
cout<<"Do u wana continue(Y/N)";
cin>>c;
if(c=='N' || c=='n')
break;
}
return 0;
}
==========================OUTPUT==============================
//output screen
user@user-ThinkPad:~/Desktop$ g++ chegg.cpp
user@user-ThinkPad:~/Desktop$ ./a.out
Enter number of nodes: 5
Please Enter edge1 2
Please Enter edge4 5
Please Enter edge1 3
Please Enter edge3 4
Please Enter edge2 5
please enter the node to be search
2 5
reachable
Do u wana continue(Y/N)y
please enter the node to be search
1 5
not reachable
Do u wana continue(Y/N)y
please enter the node to be search
1 3
reachable
Do u wana continue(Y/N)y
please enter the node to be search
1 1
reachable
Do u wana continue(Y/N)y
please enter the node to be search
5 5
reachable
Do u wana continue(Y/N)n