C++ program for Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and

Question

C++ program for

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.

Explanation / Answer

Please correct the question. if 1 -> 2 -> 5 and 3->4 and 1->3 then 1->4 should be reachable.

#include <bits/stdc++.h>
using namespace std;

// vectors = list
// vector of vectors = adjacency list
vector<vector<int> > graph;

// to check if node is visited or not
// will be used in dfs
vector<bool> isVisited;

// we will use dfs to check if a node is visible
// from given source to destination or not
bool isReachable(int source, int dest) {
if (source == dest) {
return true;
} else {

// mark current node as visited
isVisited[source] = true;

// iterate over list of neighbours and apply function recursively
// if b is reachable from a and c is reachable from b then c is reachable from a
for (int i = 0; i < graph[source].size(); ++i) {
int next = graph[source][i];
if (!isVisited[next]) {
bool isDestinationReachable = isReachable(next, dest);
if (isDestinationReachable) return true;
}
}

// clear out the current to visit to node so that we can
// visit it again for next query
isVisited[source] = false;

// we have checked for recursively all neighbours
// there is no such path so return false
return false;
}
}

int main() {
// take input number of nodes, number of edges
int n, m;
cin >> n;

// as number of edges not specified in question
// to be taken as input they are considered n - 1
// to take them as input comment the following line of code
// and replace cin >> n (above) with cin >> n >> m
m = n - 1;
  
// resize it to have n lists
graph.resize(n);
isVisited.resize(n);

// initialize all nodes "not visited"
for (int i = 0; i < n; ++i) isVisited[i] = false;

// read edges
for (int i = 0; i < m; ++i) {
int source, dest;
cin >> source >> dest;

// start node numbering from 0
source -= 1; dest -= 1;

graph[source].push_back(dest);
}

while (true) {
int source, dest;
cin >> source;

// if source = 0 this is a signal to stop taking input
if (source == 0) {
break;
}

cin >> dest;

// trim down to zero based count
source -= 1;
dest -= 1;

bool ok = isReachable(source, dest);
if (ok) cout << "reachable" << endl;
else cout << "not reachable" << endl;
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.