1.10.4 Application

• detect a cycle in the graph
  // A recursive function that uses visited[] and parent to detect 
  // cycle in subgraph reachable from vertex v. 
  bool Graph::isCyclicUtil(int v, bool visited[], int parent){ 
      // Mark the current node as visited 
      visited[v] = true; 
   
      // Recur for all the vertices adjacent to this vertex 
      list<int>::iterator i; 
      for (i = adj[v].begin(); i != adj[v].end(); ++i){ 
          // If an adjacent is not visited, then recur for that adjacent 
          if (!visited[*i])        { 
             if (isCyclicUtil(*i, visited, v)) 
                return true; 
          } 
          // If an adjacent is visited and not parent of current vertex, 
          // then there is a cycle. 
          else if (*i != parent) 
             return true; 
      } 
      return false; 
  }