//mazegraph.cpp #include mazegraph.h #include mazegraph::mazegraph() { int vertex; cin >> size; cin >> start; cin >> exit; assert(0 vertex; while(vertex != -1) { adjList[i] =

//mazegraph.cpp

#include "mazegraph.h" #include

mazegraph::mazegraph() { int vertex; cin >> size; cin >> start; cin >> exit; assert(0 <= start && start < size); assert(0 <= exit && exit < size);

adjList.resize(size,NULL); for(int i = 0; i < size; ++i) { cin >> vertex; while(vertex != -1) { adjList[i] = new vnode(vertex,adjList[i]); // insert at begining cin >> vertex; }

//mazegraph.h

#ifndef MZGRPH #define MZGRPH

#include #include #include

using namespace std;

struct vnode { int v; // vertex vnode *next; vnode(int u, vnode *n): v(u), next(n){}; };

typedef vnode * vnodeptr;

class mazegraph { public: mazegraph(); // interactive constructor using cin vector adj() {return adjList;} friend stack dfsFindExit(mazegraph &M); private: int size; int start; int exit; vector adjList; };

#endif

//pathfinder.cpp

#include "pathfinder.h" #include #include

using namespace std;

stack dfsFindExit(mazegraph &M) { int start = M.start, exit = M.exit, current, nbr; stack path; vector visited(M.size,false); vnodeptr cursor; // Complete the code for this function below

}

//pathfinder.h

#include "mazegraph.h"

stack dfsFindExit(mazegraph &M);

//pathtester.cpp

#include #include "mazegraph.h" #include "pathfinder.h"

using namespace std;

void printBottomToTop(stack S)

{ if(S.empty()) return; else { int topguy = S.top(); S.pop(); printBottomToTop(S); cout << topguy << " "; } }

int main() { mazegraph M; stack wayout = dfsFindExit(M);

if(wayout.empty()) cout << "No way out" << endl; else { printBottomToTop(wayout); cout << endl; } }

//input

6 2 3 2 3 5 -1 5 3 2 4 -1 0 1 4 5 -1 0 1 5 -1 1 2 5 -1 0 1 2 3 4 -1

//correct

2 5 4 1 3

//cut_tester.cpp

#include "graph.h"using namespace std; int main(){ graph G; if(!G.connected(-1)) { cout << "Graph is not connected; terminating" << endl; return 1; } vector cutpoints = G.get_cutpoints(); cout << "Number of cutpoints: " << cutpoints.size() << endl; cout << "Cutpoints: "; for(int i = 0; i < cutpoints.size(); ++i) cout << cutpoints[i] << " "; cout << endl; return 0;}

//graph.cpp

#include "graph.h"#include #include graph::graph(){ int vertex; cin >> size; adjList.resize(size,NULL); for(int i = 0; i < size; ++i) { cin >> vertex; while(vertex != -1) {

adjList[i] = new vnode(vertex,adjList[i]); // insert at begining cin >> vertex; } }} int firstFalse(vector b){ int i = 0; while(i < b.size() && b[i]) i += 1; return i;}bool all(vector b){ for(int i = 0; i < b.size(); ++i) if(!b[i]) return false; return true;} void graph::dfs(vector &visited){ int start = firstFalse(visited); int nbr, current = start; stack S; vnodeptr cursor; visited[start] = true; S.push(start); // Supply the remaining code below } bool graph::connected(int excluded = -1){ vector visited(size,false); if(excluded != -1) visited[excluded] = true; // Supply the remaining code below } vector graph::get_cutpoints(){ vector cutpts; // Supply the remaining code below

}

//graph.h

#ifndef GRPH#define GRPH #include #include using namespace std; struct vnode { int vertex; vnode *next; vnode(int u, vnode *n): vertex(u), next(n){};}; typedef vnode * vnodeptr; class graph { public: graph(); // interactive constructor using cin bool connected(int excluded); void dfs(vector &visited); vector get_cutpoints(); private: int size; vector adjList;}; #endif