Given a directed graph. The task is complete the function vector shortestPath(int V, vector adj[], int target) given the driver codes to find a shortest path from vertex 0 to a target vertex v. You may adapt Breadth First Traversal of this graph starting from 0 to achieve this goal. Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration. Example
C++
Use the driver code typed out below to answer the question.
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution {
public:
// Function to return a path
vector <int> shortestPath(int V, vector adj[], int target) {
// Enter code here!
}
};
// { Driver Code Starts.
int main() {
int tc;
cin >> tc;
while (tc--) {
int V, E, target;
cin >> V >> E >> target;
vector adj[V];
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
// adj[v].push_back(u);
}
// string s1;
// cin>>s1;
Solution obj;
vector ans = obj. shortestPath(V, adj, target);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
} // } Driver Code Ends
Given a directed graph. The task is complete the function vector <int> shortestPath(int V, vector adj[], int target) given the driver codes to find a shortest path from vertex 0 to a target vertex v. You may adapt Breadth First Traversal of this graph starting from 0 to achieve this goal. Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.
Example
Input:
6 8 2
0 1
0 4
1 2
0 3
3 5
4 5
5 2
3 1
Output:
0 1 2
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
