Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK
Created January 22, 2020 17:49
Show Gist options
  • Save SuryaPratapK/e84cf8624da8a690f11d5ce31745b808 to your computer and use it in GitHub Desktop.
Save SuryaPratapK/e84cf8624da8a690f11d5ce31745b808 to your computer and use it in GitHub Desktop.
// { 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
@rahulkushwaha12
Copy link

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

@revanth004-sys
Copy link

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

@V15hnu24
Copy link

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);
...................
..............
}

@surabhi020791
Copy link

What will be the time complexity?

@mks21998
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment