//--- Graph
//===========

#include <vector>
#include <iostream>
using namespace std;

template <class DataType>
class Graph
{
// Operations
public:

/* Retrieve data value in a given vertex.
 *
 * Receive:  Graph containing this function (implicitly)
 *           Number k of a vertex
 * Return:   Data value stored in vertex #k
 **********************************************************/
DataType Data(int k) const;

/* Input operator to build the edge-list representation of
 * the graph from user input.
 *
 * Receive:   istream in and graph (implicitly)
 *            number of vertices and edges  
 * Input:     Vertices and edges of graph
 * Pass back: modified istream in
 **********************************************************/
void Read(istream & in, int numVertices, int numEdges);

/* Do a depth-first search of graph from start vertex.
 *
 * Receive:   Graph containing this function (implicitly)
 *            Vector unvisited with unvisited[i] = true if 
 *              vertex i has not yet been visited, and
 *              false otherwise
 * Pass back: Updated list unvisited
 * Output:    Depends on the type of processing done when
 *              a node is visited
*********************************************************/
void DepthFirstSearch(int start, vector<bool> & unvisited);

/* Check if graph is connected.
 *
 * Receive: Graph containing this function (implicitly)
 * Return:  True if graph is connected, false if not
 *********************************************************/
bool Connected();

private:
// Edge Nodes
  struct EdgeNode
  {
    int vertex[3];         // for convenience, use
    EdgeNode * link[3];    //   1 and 2 for indices
  };
  typedef EdgeNode * EdgePointer;

// "Head nodes" of edge lists
  struct VertexInfo
  {
    DataType data;         // data value in vertex
    EdgePointer first;     // pointer to first edge node
  };

// Data Members
  vector<VertexInfo> v;
}; // end of class declaration


//--- Definition of Data()
template <class DataType>
inline DataType Graph<DataType>::Data(int k) const
{ return v[k].data; }


//--- Definition of Read()
template <class DataType>
void Graph<DataType>::Read(istream & in, int numVertices, int numEdges)
{
  Graph<DataType>::VertexInfo vi;
  v.push_back(vi);  // use indices 1, 2, . . .

  // Create "head nodes"
  cout << "Enter label of vertex:\n";
  for (int i = 1; i <= numVertices; i++)
  {
    cout << "  " << i << ": ";
    in >>vi.data;
    vi.first = 0;
    v.push_back(vi);
  }

  int endpoint;       // endpoint of an edge   
  // Create edge lists
  cout << "Enter endpoints of edge\n";
  for (int i = 1; i <= numEdges; i++)
  {
    cout << "  " << i << ": ";
    EdgePointer newPtr = new EdgeNode;
    for (int j = 1; j <= 2; j++)
    {
      in >> endpoint;
      // insert new edge node at beginning
      // of edge list for endpoint
      newPtr->vertex[j] = endpoint;
      newPtr->link[j] = v[endpoint].first;
      v[endpoint].first = newPtr;
    }
  }
}


//--- Utility function to check if all nodes have been visited.
//    Receive: unvisited
//    Return:  true if all vertices, false if not
//--------------------------------------------------------------

bool AnyLeft(const vector<bool> & unvisited)
{
  for (int i = 1; i < unvisited.size(); i++)
    if (unvisited[i])
      return true;
  return false;
}

//-- Definition of DepthFirstSearch()
template <class DataType>
void Graph<DataType>
::DepthFirstSearch(int start, vector<bool> & unvisited)
{
  // --- Insert statements here to process visited node
  // Mark start visited, and initialize pointer 
  // to its first edge node to begin DFS.
  unvisited[start] = false; 
  Graph<DataType>::EdgePointer ptr = v[start].first;

  while(AnyLeft(unvisited) && ptr != 0)
  {
    // Determine which end of edge is start
    int startEnd = 1,   
        otherEnd = 2;
    if (ptr->vertex[1] != start)
    { startEnd = 2; otherEnd = 1;}

    // Start new (recursive) DFS from vertex at other end
    // if it hasn't already been visited
    int newStart = ptr->vertex[otherEnd];
    if (unvisited[newStart])
      DepthFirstSearch(newStart, unvisited);
    // Move to next edge node
    ptr = ptr->link[startEnd];
  }
}


//-- Definition of Connected()
template <class DataType>
bool Graph<DataType>::Connected()
{
  vector<bool> unvisited(v.size(), true);
  DepthFirstSearch(1, unvisited);
  return !AnyLeft(unvisited);
}