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
@nehaaa18
Copy link

nehaaa18 commented Sep 7, 2020

in the main method, u and v are what?

@Soubhik752blaze
Copy link

Soubhik752blaze commented Sep 8, 2020

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

@ak1484
Copy link

ak1484 commented Oct 9, 2020

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++

@Anirgb00
Copy link

Anirgb00 commented Oct 23, 2020

@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

@themagellanic
Copy link

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

@Anirgb00
Copy link

Anirgb00 commented Oct 30, 2020

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

@sohantipre
Copy link

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

@themagellanic
Copy link

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

@Himanshu3198
Copy link

it gives TLE ON gfg

@123-hub
Copy link

123-hub commented May 13, 2021

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;

}

@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