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

GfG-Problem Link: bit.ly/3QwPVsi
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

[@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

[@adityasinghjadon5760]

when i used pathVis array instead of vis arr in "traverse for adjacent nodes" section {Line -15} . I am getting TLE, could anyone explain me why?

[@praveen._.m._.]

@@adityasinghjadon5760 path[I] came back to zero when cycle not in that path,so the node never consider as visited ,time limit exceed

[@excayush1011]

yes

[@mrbug100yearsago5]

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 ❣

[@coder_07]

did you took TUF+ subscription ? like u wrote "can anything for striver"

[@beinghappy9223]

The concept of visited and path visited is really amazing

[@Moch117]

Facts. This concept seems to stick with me the most

[@Lalala_1701]

Visited pathVisited rocks

[@yashgupta6797]

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.

[@unknown2003august]

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

[@RishabhSharma-p9o]

private boolean DFS(int i,int[] vis,ArrayList 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.

[@saimasyeda6544]

Can you please tell why we always declare the other function as private?

[@aniketainapur3315]

@@saimasyeda6544 Doesn't Matter here, Its just one of OOPS Concept

[@saimasyeda6544]

@@aniketainapur3315 OK thanks

[@harshith4549]

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

[@vishalsujaykumar5245]

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

[@santoshb7776]

visited[nbr] = 2; this statement in line number 12 is not necessary right, because however in dfs call you will be marking it as 2

[@techy_ms-e2m]

@@santoshb7776 Yes

[@priyanshkumar17]

@@santoshb7776 Yeah

[@arnabsarkar5245]

public boolean dfsTechnique2(int V, ArrayList adj) { // code here int[] vis = new int[V]; for (int i = 0; i < V; i++) { if (vis[i] == 0) { if (dfs2(i, adj, vis)) { return true; } } } return false; } public boolean dfs2(int node, ArrayList adj, int[] vis) { vis[node] = 2; ArrayList neigh = adj.get(node); for (int i : neigh) { if (vis[i] == 0) { if (dfs2(i, adj, vis)) { return true; } } else { if (vis[i] == 2) { return true; } } } vis[node] = 1; return false; } This is my space otpimized code, giving me TLE in case 201.

[@Siddhartha_Bose]

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

[@wolfpride9416]

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

[@prateekshrivastava2802]

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

[@cinime]

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

[@cypher7536]

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

[@Kartik-s8r]

BELOW IS THE CODE USING SINGLE VISITED ARRAY (VALUE=1 FOR VISITED & VALUE=2 FOR PATHVISITED) . . . . . class Solution { public: bool detectCycleDFS(int node, vector &visited, vector adj[]) { // Put node into Answer visited[node] = 1; visited[node] = 2; // pathVisited // Run DFS on all it's non-visited neighbours for(auto neigh:adj[node]) { if(!visited[neigh]) { if(detectCycleDFS(neigh, visited, adj)) return true; // If any one of the DFS calls returns a True, we keep on returning True } else if(visited[neigh] == 2) { // If a node is visited again on same path, cycle is detected (visited node is also pathVisited) return true; } } // On coming back, omit the node from pathVisited as path is gonna be different now visited[node] = 1; return false; } bool isCyclic(int V, vector adj[]) { vector visited(V, 0); // Behaves as both visited (value = 1) & pathVisited (value = 2) for(int i=0; i

[@rahulnegi4027]

bro just use visited[node] = 2; no need for the statement above it

[@sumitchakrabortystudy651]

the idea of using just 1 array is amazing

[@anaghakr9900]

Backtracking explanation is fantastic

[@santanu29]

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

[@abytespaceneeded]

// single visited array code: class Solution { public: bool dfs(int s, vector &visited, vector adj[]) { visited[s] += 1; visited[s] += 1; for(int ele: adj[s]) { if(visited[ele] == 0) { if(dfs(ele, visited, adj) == true) return true; } else if(visited[ele] == 2) { return true; } } visited[s] -= 1;; return false; } // Function to detect cycle in a directed graph. bool isCyclic(int V, vector adj[]) { vector visited(V, 0); for(int i=0;i

[@simmi641]

I am glad that we have Striver❣he's real gem I expected ki mera Bf inti achi DSA padhata muje khud to amazon chla gaya Kash Striver mera bf hota ,but it okay ,i have Striver on utube , i am learning and growing

[@bhaktisharma9681]

Very helpful video, thank you so much bhaiya!!

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@meghapaul1496]

Using single vis array : class Solution { private: bool dfs(int node,vector adj[], vector&vis){ vis[node]=2; for(auto it : adj[node]){ if(!vis[it]){ if(dfs(it,adj,vis)){ return true; } } else if(vis[it]==2){ return true; } } vis[node]=1; return false; } public: // Function to detect cycle in a directed graph. bool isCyclic(int V, vector adj[]) { // code here vectorvis(V,0); for(int i =0 ; i

[@chitranjansingh8432]

nice one

[@fivexx469]

isnt it same because any way you are using int data type for marking vis array which is already taking double space in comparison to bool data type?

[@suyashmishra6946]

@@fivexx469 Yeah its same

[@oqant0424]

Understood! Super awesome explanation

[@abhijeetkumar2970]

Code using only single visited array: class Solution { bool util(vector adj[],int u,vector &vis){ vis[u] = 1; for(auto v:adj[u]){ if(vis[v] == -1){ if(util(adj,v,vis)) return true; }else if(vis[v] == 1) return true; } vis[u] = 0; return false; } public: // Function to detect cycle in a directed graph. bool isCyclic(int V, vector adj[]) { // code here vector vis(V,-1); for(int i=0;i

[@VarunMurthy-l9b]

These videos are incredible

[@harshvardhansingh2272]

understood striver as always easy and great explanation

[@preetisahani5054]

brilliantly explained

[@Desi_Debugger]

understood striver bhaiyaaaaa.................

[@madhuryareddy3994]

Thanks man for the wonderful explanation, Grateful!

[@kushalkollu8628]

He is the OG

[@aayushgakhar3525]

homework for only vis arr , we can take cnt as2 each time we visit(as it signifies vis +path) and while returning we could set it to 1 and if vis[node]&&vis[node]==2 return true;

[@uditech7736]

This is an excellent explanation.

[@ketanjain3881]

this series is too good!

[@rohitanand7071]

Using one visited array bool dfs(int node, int vis[], vector adj[]) { vis[node] = 2; // visit adjacent nodes for(auto adjacentNode: adj[node]) { // unvisited adjacent node if(!vis[adjacentNode]) { if(dfs(adjacentNode,vis,adj)) { return true; } } else if(vis[adjacentNode]==2) return true; } vis[node]=1; return false; }

[@jewelchowdhury9752]

Thanks bro for ur awesome work....BTW 16:41😋

[@adithyab967]

C++ code using a single Visited array : bool dfs(vector adj[],vector&visited,int start){ visited[start] = 1; int temp = visited[start]; visited[start] = 2; for(auto &neighbour : adj[start]){ if(visited[neighbour]==0){ if(dfs(adj,visited,neighbour)==true) return true; } else if(visited[neighbour] == 2){ return true; } } visited[start] = temp; return false; } bool isCyclic(int V, vector adj[]) { vectorvisited(V,0); for(int i=0;i

[@moonlight-td8ed]

it is an easy problem, just we have to get the logic of that we are in the same path, thank you STRIVER

[@dipaligangawane980]

Understood. Really wonderful lecture series.

[@abhignapalamoor1174]

Understood! Wow 🤯

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@ShahnazKhan-j4i]

You are amazing, keep doing these

[@kingfisher7348]

Next level explanation!💥

[@amanbhadani8840]

Using just visited single array(Without using dfsvis array) solution:- class Solution { public: bool checkCycle(int node,int V,vector&vis,vectoradj[]) { vis[node]=2; for(auto it:adj[node]) { if(vis[it]==0){ if(checkCycle(it,V,vis,adj)==true) return true; } else if(vis[it]==2) return true; } vis[node]=1; return false; } // Function to detect cycle in a directed graph. bool isCyclic(int V, vector adj[]) { // code here vectorvis(V,0); for(int i=0;i

[@tromboner6061]

we could have also created new boolean[V] for pathVis[] for each vertex instead of working with single array to save memory

[@SachinKumar-zs6hm]

Understood!! Thanks a lot Striver

[@p_s1dharth]

blown away, understood

[@abhijeetkumar2970]

understoood

[@NiravRathod-p5n]

space complexity of 2 boolean array < 1 int/short array

[@ramuchiluveru1056]

Thank you soo much bhayya.. for your wondefull explaination using the single visited array bool dfs(int node,vector adj[],vector visited) { visited[node]++; ..marking as visited visited[node]++; //marking its path by increment for(auto i: adj[node]) { if (visited[i] == 0) { if(dfs(i, adj, visited)) return true; } else if (visited[node] == 2) return true; } visited[node]--; //unpathing return false; } bool isCyclic(vector& edges, int v, int e) { // Write your code here vector adj[v]; //creating adj list for(auto edge: edges) { int from = edge[0]; int to = edge[1]; adj[from].push_back(to); } vector visited(v,0); // vector path(v,0); for(int i=0;i

[@AyushGupta-ux4gq]

for(auto i: adj[node]) { if (visited[i] == 0) { if(dfs(i, adj, visited)) return true; } else if (visited[I] == 2) return true; } *CORRECT CODE*

[@DevashishJose]

Understood, thank you so much.

[@AnkushMallickOriginal]

Solution: class Solution { private: bool dfsCheck(int node, vector adj[], int visited[]){ visited[node] = 2; for(auto it: adj[node]){ if(visited[it] == 0){ if(dfsCheck(it,adj,visited) == true){ return true; } } else if(visited[it] == 2){ return true; } } visited[node] = 1; return false; } public: // Function to detect cycle in a directed graph. bool isCyclic(int V, vector adj[]) { // code here int visited[V] = {0}; for(int i = 0;i < V;i++){ if(visited[i] == 0){ if(dfsCheck(i,adj,visited) == true){ return true; } } } return false; } };

[@jasminmalhot7829]

Really ,youre taking us f/w..❤

[@sukhpreetsingh5200]

Understood!!! awesome as usual

[@harkeshbirman]

I don't know if it's just me but Your keystrokes sounds funny🙃

[@manishprajapati8544]

mast video hai bhai 👌👌

[@KS0607]

great crisp xplntion

[@jagratgupta8392]

understood very nicely sir great explaination sir

[@ishangujarathi10]

op intuition and amazing concept!! tysm

[@digvijay1228]

The moment i heard path, I stopped the video and coded the solution and it passed. Thanks to recursion playlist (subsequence pattern). DFS + subsequence. Understood!!! Code Reference: public boolean isCyclic(int V, ArrayList adj) { Set vis = new HashSet(); for(int i=0; i

[@preetichib2254]

Loved this video🎉

[@RS-zh1vc]

thank you Striver

[@syedmohdzeeshanali8247]

Haven't seen the video yet but will definitely edit this comment to 'understood' after watching it. :) Thanks Striver Bhaiiyyaaaaaaaaaa

[@udaypratapsingh8923]

i think you forgot ? go huuryy and edit this

[@amaan6017]

Hello bro... Waiting for your "Understood".

[@babuchkjethia822]

Still wiating

[@theganeshpatil]

bhai dekh le video, placement season aa raha hai

[@ashurajput6916]

Bhai ab to samajh jaa...

[@chiranjiveethakur9889]

Great explanation!!

[@devanshupadhyay2658]

Best in the game aur isme do rai nahi !!

[@thomasfrank132]

You are a legend

[@KratosProton]

Great explaination

[@AnkitYadav-hx8im]

You should have made videos by doing some codes in c and some codes in java. That would be able to cater to both java and c students

[@UECAshutoshKumar]

Thank you sir

[@sivammohapatra1478]

16:28 bool dfs(int node, vector adj[], int vis[]){ vis[node]=2; for(auto it:adj[node]){ if(!vis[it]){ if(dfs(it, adj, vis)==true) return true; } else if(vis[it]==2) return true; } vis[node]=1; return false; } //main function remains the same

[@namantiwari6581]

Striver bhaiya kindly fix the numbering for this particular video as it is showing at last instead of the order that this particular video has to be in..🙂🙂🙂🙃🙃

[@Pranauv]

understood! thanks a lot sir!

[@VenugopalaSwamy-fb3se]

instead of using path visited array we can use backtracking approach also

[@tecnicalworld6957]

Great explaination 👍

[@Learnprogramming-q7f]

Thank you bhaiya

[@nitishdasgupta1704]

class Solution { bool Detect(int s,vectoradj[],vector&visited){ visited[s]=2; for(auto node:adj[s]){ if(visited[node]==0 && Detect(node,adj,visited)){ return true; } else if(visited[node]==2){ return true; } } visited[s]=1; return false; } public: // Function to detect cycle in a directed graph. bool isCyclic(int V, vector adj[]) { // code here vectorvisited(V,0); // vectorpath(V,false); for(int i=0;i

[@aayushgakhar3525]

great intitution

[@parallax8916]

I completed the homework u gave in a min Thank u soo much for making it soo easyy!!!! U r a legend!!!

[@Divas_Sagta_09]

4:32 - in the same recursive stack

[@saisriangajala3338]

Can we find the Cycle using BFs ?? In BFs we are not exploring in single path unlike in DFs, I think in BFs we cannot determine that we encountered the node in same path or not. Correct me if I am wrong

[@takeUforward]

We will have an algorithms for bfs as well in coming lectures

[@sindhukambam]

Understood! thank you very much!!

[@bhavyagautam8036]

Using single visited array bool dfs(int node,vector &vis,vector adj[]) { vis[node] = 2;//vis[node] = 2 means that the node is visited as well as path visited. for(auto it: adj[node]) { if(vis[it]==0)//If the node has not been visited { if(dfs(it,vis,adj)==true)return true; } else if(vis[it] ==2)//If the node is already visited and also path visited { return true; } } vis[node] = 1;//Node is visited but not path visited. return false; } bool isCyclic(int V, vector adj[]) { // code here vector vis(V,0); for(int i=0;i

[@vikashrock5518]

Code for using single extra vis array. bool dfs(int node, vector adj[], vector &vis) { vis[node] = 2; for(auto &it: adj[node]) { if(!vis[it]) { if(dfs(it, adj, vis)) return true; } else if(vis[it]==2) return true; } vis[node] = 1; return false; } bool isCyclic(int V, vector adj[]) { vector vis(V, 0); for(int i=0;i

[@StellarDev]

Thanks for the helpful tutorial! :)

[@uvs_6032]

*Single Visited Array Code* /* vis[node] == 1 // node was visited before but not part of curr path vis[node] == 2 // node is visited and part of curr Path vis[node] == 0 // unvisited */ class Solution { public: bool dfs(int node , vector& vis , vector adj[]) { vis[node] = 2; for(auto child : adj[node]) { if(vis[child] == 2) return true; if(!vis[child] and dfs(child , vis , adj)) return true; } vis[node] = 1; return false; } bool isCyclic(int V, vector adj[]) { vector vis(V , 0); for(int i = 0 ; i < V ; i++) { if(!vis[i] and dfs(i , vis , adj)) return true; } return false; } };

[@mathematics7746]

thank you so much and also understood

[@_sf_editz1870]

so we just analyse the recurrsion stack if we visited that node again or not superb algorithm

[@shubham57641]

Tagline of this video is visited on same path then cyclic ❤

[@adityasaxena6971]

Understood 💯💯💯

[@The_Shubham_Soni]

On LEETCODE- Course Schedule (Q-207)

[@monikagadewar4927]

Just understood 😀

[@kr_ankit123]

I am glad that I am able to develop the logic and it has been possible after watching your lectures. Thanks a lot Striver. Solution without using path array: private: bool dfs(vector adj[],vector&vis,int node){ vis[node]=1; for(int it:adj[node]){ if(vis[it]==0){ if(dfs(adj,vis,it))return true; } else{ if(vis[it] == 1)return true; } // cout

[@fluxcy2396]

Your code is far far from optimal, infact its a brute-force solution. It's computing the same thing over and over again. Here's a correct solution in just a single visited array- 2 means the node is in the current path Once we are returning after exploring a given path, we change visited[currNode] from 2 to 1 Which means the current node is not in the current path anymore, however, it has been visited and does not have a cycle either ``` class Solution { private: bool hasCycle(int currNode, vector adj[], int visited[]){ visited[currNode] = 2; for(int nextNode : adj[currNode]){ if(!visited[nextNode]){ if(hasCycle(nextNode, adj, visited)) return true; } else if(visited[nextNode] == 2){ return true; } } visited[currNode] = 1; return false; } public: bool isCyclic(int V, vector adj[]) { int visited[V] = {0}; for(int node = 0; node < V; node++){ if(!visited[node] && hasCycle(node, adj, visited)) return true; } return false; } }; ```

[@ambastaaashishkumarsanjayk2729]

Understood, Thanks

[@TheBaljitSingh]

Space complexity: O(N) bool dfs(int node, vector adj[], int vis[]){ // vis[node] = 1; vis[node] = 2; // pathVis[node] = 2; for(auto adjacentNode: adj[node]){ // cout

[@vishious14]

Amazing. My approach is just as this

[@atharvadeshmukh6328]

understood, thank you!

[@subhadeepghosh2813]

Maza aa gya vai

[@khyatikakkar9259]

Understood sir

[@nilaychatterjee54]

Understood... but you already have this topic covered in your Graph series... will that video be replaced by this..? Or is it a beginning of a new series altogether...?

[@takeUforward]

Community post refer

[@ANURAGSINGH-nl2ll]

understood thank you

[@imranshaikh115]

Just Awesome

[@Piyushraj0]

Understood 😊