Detect cycle in a directed graph

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


 // } Driver Code Ends
/*  Function to check if the given graph contains cycle
*   V: number of vertices
*   adj[]: representation of graph
*/
bool isCyclic_util(vector<int> adj[], vector<bool> visited, int curr)
{
    if(visited[curr]==true)
        return true;
    
    visited[curr] = true;
    bool FLAG = false;
    for(int i=0;i<adj[curr].size();++i)
    {
        FLAG = isCyclic_util(adj, visited, adj[curr][i]);
        if(FLAG==true)
            return true;
    }
    return false;
}

bool isCyclic(int V, vector<int> adj[])
{
   vector<bool> visited(V,false);
   bool FLAG = false;
   for(int i=0;i<V;++i)
   {
           visited[i] = true;
           for(int j=0;j<adj[i].size();++j)
           {
               FLAG = isCyclic_util(adj,visited,adj[i][j]);
               if(FLAG==true)
                   return true;
           }
           visited[i] = false;
   }
   return false;
}

// { Driver Code Starts.

int main() {
	
	int t;
	cin >> t;
	
	while(t--){
	    
	    int v, e;
	    cin >> v >> e;
	    
	    vector<int> adj[v];
	    
	    for(int i =0;i<e;i++){
	        int u, v;
	        cin >> u >> v;
	        adj[u].push_back(v);
	    }
	    
	    cout << isCyclic(v, adj) << endl;
	    
	}
	
	return 0;
}  // } Driver Code Ends

in the main method, u and v are what?

@nehaaa18 these are edge connected two vertices from u to v direction

i think you missed one line in isCycle_util after completing the for loop you need to make again visited[curr]=false..... because i try to solve this code in py and i was stucking on this point because it give always true .....or maybe this problem is not in c++

@ak

i think you missed one line in isCycle_util after completing the for loop you need to make again visited[curr]=false..... because i try to solve this code in py and i was stucking on this point because it give always true .....or maybe this problem is not in c++

may you please tell us what are changed are you taking about by providing us the code in c++ version or python

You have taken v at two places .Is this code not showing error?

You have taken v at two places .Is this code not showing error?

which "v" are you talking about

1. "v" small v = the number of vertices
2. "V" capital v = Current node

This code is taking too much time . please , provide optimized solution.

You have taken v at two places .Is this code not showing error?

which "v" are you talking about

1. "v" small v = the number of vertices
2. "V" capital v = Current node

while(t--){

    int v, e;
    cin >> v >> e;
    
    vector<int> adj[v];
    
    for(int i =0;i<e;i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    
    cout << isCyclic(v, adj) << endl;
    
}

see v is declared two time

it gives TLE ON gfg

correct code is here;;;;;

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define loop(i,a,b) for(int i = a; i < b; i++)
#define revloop(i,a,b) for(int i = a; i > b; i--)
#define mod 1000000007
#define inf (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll,pair<ll,ll>>
#define goog(tno) cout << "Case #" << tno <<": "
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define read(x) int x; cin >> x
using namespace std;

void init_code(){
fast_io;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}

bool isCyclic_util(vector adj[], vector visited, int curr)
{
if(visited[curr]==true)
return true;

visited[curr] = true;
bool FLAG = false;
for(int i=0;i<adj[curr].size();++i)
{
    FLAG = isCyclic_util(adj, visited, adj[curr][i]);
    if(FLAG==true)
        return true;
}

visited[curr]=false;
return false;

}

bool isCyclic(int V, vector adj[])
{
vector visited(V,false);
bool FLAG = false;
for(int i=0;i<V;++i)
{
visited[i] = true;
for(int j=0;j<adj[i].size();++j)
{
FLAG = isCyclic_util(adj,visited,adj[i][j]);
if(FLAG==true)
return true;
}
visited[i] = false;
}
return false;
}

int main() {
init_code();
int t;
cin >> t;

while(t--){

  int v, e;
  cin >> v >> e;
  
  vector<int> adj[v];
  
  for(int i =0;i<e;i++){
      int u, p;
      cin >> u >> p;
      adj[u].push_back(p);
  }
  
  if(isCyclic(v,adj))
    cout<<"cycle is found";
  else
    cout<<"not found";

}
return 0;

}

checkout this, simple DFS solution with memoization, this will pass all test cases
pardon for golang code, but it is understandable
https://gist.github.com/rahulkushwaha12/775da82fa280effce68991d92ea9c544

sir, after line 23, is it needed to put visited[curr]==false or it takes directly false. can you explain this sir..???

Same doubt as we are taking completely new visited array we have to make all the elements false after every iteration of the for loop.
Here is the psuedocode
.............
...........
for .....{
visited[] = false*len(visited);
...................
..............
}

What will be the time complexity?

What will be the time complexity?

Average / In General : O(V+E)
Words Case : O(V^{2}) when every node is connected to all the other nodes.