//--- fig14-2.cpp
//===============
/* Program to determine if a graph is connected.
 *
 *  Input:  Number of vertices and number of edges of a graph,
 *          labels for the vertices, and endpoints of the edges 
 *          User response
 *  Output: Message indicating whether the graph is connected and
 *          list of unreachable vertices from first vertex if
 *          user asks for it.
j*****************************************************************/

#include "Graph"
#include <iostream>
using namespace std;

int main()
{
  int numVertices,         // number of vertices in the graph
      numEdges;            //   "     "  edges   "   "    "
  cout << "Enter number of vertices and number of edges in graph: ";
  cin >> numVertices >> numEdges;

  Graph<char> g;
  g.Read(cin, numVertices, numEdges);

  cout << "Graph is ";
  if (g.Connected())
    cout << "connected.\n";
  else
  {
    cout << "not connected.\n"
            "Would you like to see which vertices are not\n"
            "reachable from vertex 1 (" << g.Data(1) << ") -- (Y or N)? ";
    char response;
    cin >> response;
    if (response == 'y' || response == 'Y')
    {
      cout << "They are the following: \n";
      vector<bool> unreachable(numVertices+1, true);
      g.DepthFirstSearch(1, unreachable);
      for (int i = 1; i < unreachable.size(); i++)
        if (unreachable[i])
          cout << "Vertex " << i << " (" << g.Data(i) << ")\n";
    }
    cout << endl;
  }
}