Use the template code given and fill /// the empty space left with the codes at the two parts. Again provide |V| and |E| in the first input line, followed by |E| number of lines specifying edges/arcs in a graph and the Node id starts from 0. Use depth-first search function for an undirected graph and Allow Time Complexity: O(n+m)

#include using namespace std;

// } Driver Code Ends class Solution { public: // Function to return Depth First Traversal of given graph. vector dfsOfGraph(int V, vector adj[]) { vector Visited(V, false); vector S; // for storing results (in visit order) stack ToExplore; // for storing to-be-explored vertices //// //// Fill out this part! //// return S; }

// Function to return Breadth First Traversal of given graph. vector bfsOfGraph(int V, vector adj[]) { vector Visited(V, false); vector S; // for storing results (in visit order) queue ToExplore; // for storing to-be-explored vertices

//// //// Fill out this part! //// ////

}

};

/**** Driver codes - DO NOT CHNAGE ****/

int main() {

int V, E; cout << "Enter sizes of V and E: " <> V >> E;

vector adj[V]; cout << "Enter edges (pairs of nodes) separated by newline: " <> u >> v; adj[u].push_back(v); }

Solution obj; vector ans1 = obj.dfsOfGraph(V, adj); cout << "Answer1 " << endl; for (int i = 0; i < ans1.size(); i++) { cout << ans1[i] << " "; } cout << endl;

vector ans2 = obj.bfsOfGraph(V, adj); cout << "Answer2 " << endl; for (int i = 0; i < ans2.size(); i++) { cout << ans2[i] << " "; } cout << endl;

return 0; } +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Test Cases

6 8

7 3

7 8

8 4

8 5

8 6

8 7

Output1

0 1 2 3 5 7 8 4 6

Output2

0 1 2 3 4 6 5 7 8