Detect Cycle in a Directed Graph

Given a directed graph, check if the graph contains cycle(s) or not. The detailed description of the problem can be found here.

Solution: DFS is employed to solve this problem. It is to be noted that it does not mean we get a cycle when a visited node is encountered again. To detect the cycles, we need to use a container to record all the nodes we've visited along the current path. If the next node we are visiting has already been visited and recorded in the container, we say we get a cycle. The following is the solution to this problem; the time complexity if O(V+E) [part of code is from geeksforgeeks]

// A C++ Program to detect cycle in a directed graph
#include<iostream>
#include <vector>
 
using std::vector;
using std::cout;
using std::endl;
 
class Graph
{
private:
    int V;  // No. of vertices
    vector<int> *adj;
    bool isCyclicUtil(int v, vector<bool> &visited, vector<bool> rs);
public:
    Graph(int v):V(v), adj(new vector<int>[V]){}
    void addEdge(int v, int w){ adj[v].push_back(w);}
    bool isCyclic();
};
 
bool Graph::isCyclicUtil(int v, vector<bool> &visited, vector<bool> recStack){
    visited[v]=true;
    recStack[v]=true;
    for(size_t i=0; i<adj[v].size(); ++i){
        int nbr = adj[v][i];
        if(!visited[nbr]){
            cout << "path: " << v << "----->" << nbr << endl;    
            if(isCyclicUtil(nbr, visited, recStack))
                return true;
        }
        else if(recStack[nbr]){
            cout << "path: " << v << "----->" << nbr << endl;    
            cout << "back edge: " << v << "----->" << nbr << endl;
            return true;
        }
    }
    return false;
}
 
bool Graph::isCyclic(){
    vector<bool> visited(V, false);
    vector<bool> recStack(V, false);
    for(int i=0; i<V; i++){
        if(!visited[i] && isCyclicUtil(i, visited, recStack))
        return true;
    }
    return false;
}
 
int main(){
    // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(2, 0);
    g.addEdge(3, 3);
 
    if(g.isCyclic())
        cout << "Graph contains cycle" << endl;
    else
        cout << "Graph doesn't contain cycle" << endl;
    return 0;
}