C++ Easy solution using DFS cycle detection


#1

void detectCycle(int u,const vector<vector> &adj,
vector &visit,vector &stack,int &res)
{
visit[u] = true;
stack[u] = true;

//visit its neighbor nodes
for(auto i: adj[u])
{
    if(!visit[i])
        detectCycle(i,adj,visit,stack,res);
    else if(stack[i])
    {
        res = 0;
        return;
    }
}
stack[u] = false;

}

int Solution::solve(int V, vector &B, vector &C)
{
int n = B.size();

//make graph for given edges
vector<vector<int>> adj(V+1);
for(int i=0;i<n;i++)
{
    adj[B[i]].push_back(C[i]);
}

vector<bool> visit(V+1,false);
vector<bool> stack(V+1,false);

//detect cycle in graph
int res = 1;
detectCycle(1,adj,visit,stack,res);
return res;

}