G-19. Detect cycle in a directed graph using DFS | Java | C++

In case you are thinking to buy courses, please check below:

---------------------------------------------------------------------------------------------------------------------------

[takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞

Do follow me on Instagram: striver_79

[mrbugyearsago]

I cant do anything to support u....
So, showing my love and support by commenting...
Hats off to all ur efforts and thanq for everything, you are doing for the community ❣

[unknownaugust]

It is now became a habit of just watch explanation and code by yourself. 😊😊
Thank you Striver, Never thought that i can be able to solve graph problem by my own in just one go

[yashgupta]

understood !!!
only youtuber who made coding easy for us.
Rest others are busy in making cringe video of 3 lpa to 1 cr lpa types video.

[beinghappy]

The concept of visited and path visited is really amazing

[shreyasgore]

Difference btw u and rest is the simplicity, proper intution and the dry run process ....beautiful explanation.

[wolfpride]

Best explanation and logic abstraction ever!!! Thanks a lot

[RishabhSharma-po]

private boolean DFS(int i, int[] vis, ArrayList<ArrayList<Integer>> adj){
vis[i]=1;
for(int it:adj.get(i)){
if(vis[it]==0){
if(DFS(it, vis, adj)){
return true;
}
}
else if(vis[it]==1){
return true;
}
}
vis[i]=2;
return false;
}

without the pathVis approach.
Great leacture.

[harshith]

Understood well and doing dry run on my own got the algo into my head. Truly amazing brother💯.

[Siddhartha_Bose]

Striver has taught us backtracking so well, this is question is a cake walk for us.😂

[cinime]

Understood! Super awesome explanation as always, thank you very much!!

[prateekshrivastava]

Using single array was new to me .... Thanks a lot man 🙏🏻❤

[vishalsujaykumar]

Using single visited array :


/*Complete the function below*/

class Solution {
// Function to detect cycle in a directed graph.
public static boolean dfs(int src, int[] visited, ArrayList<ArrayList<Integer>> adj)
{
//Mark the node as visited
visited[src] = 2;

for(int nbr : adj.get(src))
{
//If unvisited
if(visited[nbr] == 0)
{
//Mark it as same path
visited[nbr] = 2;
if(dfs(nbr, visited, adj) == true)
{
return true;
}
}
else if(visited[nbr] == 2)
{
return true;
}
}

//Backtrack to visited
visited[src] = 1;
return false;

}
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
// code here

//Space optimization using only visited array

int[] visited = new int[V];
Arrays.fill(visited, 0);


/*
0 - Unvisited
1 - Visited
2 - Same Path
*/


for(int i = 0 ; i < V ; i++)
{
if(visited[i] == 0)
{
if(dfs(i, visited, adj) == true)
{
return true;
}
}
}
return false;

}
}

[Dipanshutripathi]

Shuru majboori mai kiya tha pr ab maja aane laga hai🙂🙃😊!!!

[oqant]

Understood!
Super awesome explanation

[santanu]

Great solution and explanation. Reminds me of print all subsubsequence problem.

[cypher]

without watching understood! ❤️ cause everyone knows why..

[bhaktisharma]

Very helpful video, thank you so much bhaiya!!

[madhuryareddy]

Thanks man for the wonderful explanation, Grateful!

[sumitchakrabortystudy]

the idea of using just 1 array is amazing