Given vertex v of graph G = (V,E), we define G-v = (V-{v},E'),where E'= { e E | e is not incident with v } That is, the graph we get by deleting v and all edges having v as an endpoint Vertex v is said to be a cutpoint of connected graph G is G-v is not connected. Our goal is to find all the cutpoints of a graphWe will do this via a class methodDepth-first search is the main tool we use, although BFS could be used instead.

We will adapt depth-first search to determine if G-v is connected We use a little trick to do thisA crucial data structure used is vector visited Its obvious use is to mark vertices as visited during dfs If, after dfs terminates, the graph is connected if and only ifall entries in visited are true. But we simulate doing dfs on G-v, by initially setting visited[v] to true before starting the search This means that v will never be used to reach another vertex

FILL THE MISSISNG CODE ONLY

//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

-------------------------------------------------

//graph.cpp

#include "graph.h" #ininclude #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 }

----------------------

//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; }