Write a program that reads a graph from the console and determines whether the graph is connected. The

first line in the input contains a number that indicates the number of vertices $($n$).$ The vertices are labeled as

$0,1,...,$ n$-1.$ Each subsequent line, with the format u v$1$ v$2...,$ describes edges

$($u$,$ v$1),($u$,$ v$2),$ and so on$.$ Figure $26\mathrm{.}18$ gives the examples of two input for their corresponding

graphs.

Your program should prompt the user to enter the input, create an instance g of Graph, invoke

g$.$printEdges$()$ to display all edges, and invokes dfs$()$ to obtain an instance tree of Tree.

If tree.getNumberOfVerticeFound$()$ is the same as the number of vertices in the graph, the

graph is connected.

When

reading a line of integers, read it as a string using getline and then split it and convert to int. You can

use the stringstream to split a string separated by whitespace characters

Enter the number of vertices: $6$

The number of vertices is $6$

Enter the edges in $6$ lines:

$012$

$2$

$103$

$2034$

$31245$

$4235$

$534$

$0(0)$: $(0,1)(0,2)$

$1(1)$: $(1,0)(1,3)$

$2(2)$: $(2,0)(2,3)(2,4)$

$3(3)$: $(3,1)(3,2)(3,4)(3,5)$

$4(4)$: $(4,2)(4,3)(4,5)$

$5(5)$: $(5,3)(5,4)$

The graph is connected

Enter the number of vertices: $6$

The number of vertices is $6$

Enter the edges:

$0123$

$103$

$203$

$3012$

$45$

$54$

$0(0)$: $(0,1)(0,2)(0,3)$

$1(1)$: $(1,0)(1,3)$

$2(2)$: $(2,0)(2,3)$

$3(3)$: $(3,0)(3,1)(3,2)$

$4(4)$: $(4,5)$

$5(5)$: $(5,4)$

The graph is not connected

$//$ Search for "WRITE YOUR CODE" to complete this program

#ifndef GRAPH$\_$H

#define GRAPH$\_$H

#include

#include $//$ For implementing BFS

#include

#include $//$ For converting a number to a string

#include

#include

using namespace std;

#ifndef TREE$\_$H

#define TREE$\_$H

class Tree

$\{$

public:

$//$ Construct an empty tree

Tree$()$

$\{$

$\}$

$//$ Construct a tree with root, parent, and searchOrder

Tree$($int root, const vector& parent,

const vector& searchOrders$)$

$\{$

this$->$root $=$ root;

this$->$parent $=$ parent;

this$->$searchOrders $=$ searchOrders;

$\}$

$//$ Return the root of the tree

int getRoot$()$ const

$\{$

return root;

$\}$

$//$ Return the parent of vertex v

int getParent$($int v$)$ const

$\{$

return parent$[$v$]$;

$\}$

$//$ Return search order

vector getSearchOrders$()$ const

$\{$

return searchOrders;

$\}$

$//$ Return number of vertices found

int getNumberOfVerticesFound$()$ const

$\{$

return searchOrders.size$()$;

$\}$

$//$ Return the path of vertices from v to the root in a vector

vector getPath$($int v$)$ const

$\{$

vector path;

do

$\{$

path.push$\_$back$($v$)$;

v $=$ parent$[$v$]$;

$\}$ while $($v $!=-1)$;

return path;

$\}$

$//$ Print the whole tree

void printTree$()$ const

$\{$

cout $$ "Root is: $"$ root $$ endl;

cout $$ "Edges: $"$;

for $($unsigned i $=0$; i $$ searchOrders.size$()$; i$++)$

$\{$

if $($parent$[$searchOrders$[$i$]]!=-1)$

$\{$

$//$ Display an edge

cout parent$[$searchOrders$[$i

searchOrders$[$i;

$\}$

$\}$

cout $$ endl;

$\}$

private:

int root; $//$ The root of the tree

vector parent; $//$ Store the parent of each vertex

vector searchOrders; $//$ Store the search order

$\}$;

#endif

#ifndef EDGE$\_$H

#define EDGE$\_$H

class Edge

$\{$

public:

int u;

int v;

Edge$($int u$,$ int v$)$

$\{$

this$->$u $=$ u;

this$->$v $=$ v;

$\}$

$\}$;

#endif

template

class Graph

$\{$

public:

$//$ Construct an empty graph

Graph$()$;

$//$ Construct a graph from vertices in a vector and

$//$ edges in $2-$D array

Graph$($const vector& vertices, const int edges$[][2],$ int numberOfEdges$)$;

$//$ Construct a graph with vertices $0,1,...,$ n$-1$ and

$//$ edges in $2-$D array

Graph$($int numberOfVertices, const int edges$[][2],$ int numberOfEdges$)$;

$//$ Construct a graph from vertices and edges objects

Graph$($const vector& vertices, const vector& edges$)$;

$//$ Construct a graph with vertices $0,1,...,$ n$-1$ and

$//$ edges in a vector

Graph$($int numberOfVertices, const vector& edges$)$;

$//$ Return the number of vertices in the graph

int getSize$()$ const;

$//$ Return the degree for a specified vertex

int getDegree$($int v$)$ const;

$//$ Return the vertex for the specified index

V getVertex$($int index$)$ const;

$//$ Return the index for the specified vertex

int getIndex$($V v$)$ const;

$//$ Return the vertices in the graph

vector getVertices$()$ const;

$//$ Return the neighbors of vertex v

vector getNeighbors$($int v$)$ const;

$//$ Print the edges

void printEdges$()$ const;

$//$ Print the adjacency matrix

void printAdjacencyMatrix$()$ const;

$//$ Clear the graph

void clear$()$;

$//$ Adds a vertex to the graph

virtual bool addVertex$($const V& v$)$;

$//$ Adds an edge