fork download
copy 
  1. // C++ program to print DFS traversal from 
  2. // a given vertex in a  given graph 
  3. #include<iostream> 
  4. #include<list> 
  5. using namespace std; 
  6.  
  7. // Graph class represents a directed graph 
  8. // using adjacency list representation 
  9. class Graph 
  10. { 
  11.     int V;    // No. of vertices 
  12.  
  13.     // Pointer to an array containing 
  14.     // adjacency lists 
  15.     list<int> *adj; 
  16.  
  17.     // A recursive function used by DFS 
  18.     void DFSUtil(int v, bool visited[]); 
  19. public: 
  20.     Graph(int V);   // Constructor 
  21.  
  22.     // function to add an edge to graph 
  23.     void addEdge(int v, int w); 
  24.  
  25.     // DFS traversal of the vertices 
  26.     // reachable from v 
  27.     void DFS(int v); 
  28. }; 
  29.  
  30. Graph::Graph(int V) 
  31. { 
  32.     this->V = V; 
  33.     adj = new list<int>[V]; 
  34. } 
  35.  
  36. void Graph::addEdge(int v, int w) 
  37. { 
  38.     adj[v].push_back(w); // Add w to v’s list. 
  39. } 
  40.  
  41. void Graph::DFSUtil(int v, bool visited[]) 
  42. { 
  43.     // Mark the current node as visited and 
  44.     // print it 
  45.     visited[v] = true; 
  46.     cout << v << " "; 
  47.  
  48.     // Recur for all the vertices adjacent 
  49.     // to this vertex 
  50.     list<int>::iterator i; 
  51.     for (i = adj[v].begin(); i != adj[v].end(); ++i) 
  52.         if (!visited[*i]) 
  53.             DFSUtil(*i, visited); 
  54. } 
  55.  
  56. // DFS traversal of the vertices reachable from v. 
  57. // It uses recursive DFSUtil() 
  58. void Graph::DFS(int v) 
  59. { 
  60.     // Mark all the vertices as not visited 
  61.     bool *visited = new bool[V]; 
  62.     for (int i = 0; i < V; i++) 
  63.         visited[i] = false; 
  64.  
  65.     // Call the recursive helper function 
  66.     // to print DFS traversal 
  67.     DFSUtil(v, visited); 
  68. } 
  69.  
  70. int test() 
  71. { 
  72.     // Create a graph given in the above diagram 
  73.     Graph g(4); 
  74.     g.addEdge(0, 1); 
  75.     g.addEdge(0, 2); 
  76.     g.addEdge(1, 2); 
  77.     g.addEdge(2, 0); 
  78.     g.addEdge(2, 3); 
  79.     g.addEdge(3, 3); 
  80.  
  81.     cout << "Following is Depth First Traversal"
  82.             " (starting from vertex 2) \n"; 
  83.     g.DFS(2); 
  84.  
  85.     return 0; 
  86. }
  87.  
  88. int main() 
  89. { 
  90.     int V,A[2];
  91.     cin>>V;
  92.     Graph g(V); 
  93.     while ( cin>> A[0]>>A[1] ) {
  94.        if (A[0]<0 || A[1]<0 || A[0]>=V || A[1]>=V)
  95.            cout << A[0]<<"->"<<A[1]<<" refers to a non-existent node"<<endl;
  96.        else g.addEdge(A[0], A[1]);
  97.     }
  98.     g.DFS(2);
  99.     return 0; 
  100. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4 
1 2
2 3 
3 1 
4 2 
4 1
stdout
copy 
4->2 refers to a non-existent node
4->1 refers to a non-existent node
2 3 1
https://ideone.com/MKbCIp
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!