G-20. Find Eventual Safe States - DFS

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

[@artofwrick]

Your dfs cycle explanation is good enough. That one video does the charm of other questions.

[@manthenanagendra1077]

this man will be remembered for so long for his work

[@kritisingh3194]

We can eliminate the check array and just use if(pathVis[i] == 0) to get the safe nodes and use the absolute same code as cycle detection in directed graph, just add this in end: List res = new ArrayList(); for(int i=0; i

[@takeUforward]

Makes sense! The check array was added to increase the understanding :) Good to see such comments 💯

[@kritisingh3194]

@@takeUforward Thanks for the quality content! :D

[@rishavsaha5254]

Then this question will boil down to checking only the "false" pathVis nodes. Nice!

[@eshaanpandey7353]

@@rishavsaha5254 Exactly

[@-Corvo_Attano]

*JAVA CODE USING SINGLE VIS[] ARRAY* class Solution { private static boolean dfs(int num , int vis[] , List adj){ vis[num] = 1; for(int it : adj.get(num)){ if(vis[it] == 0){ if(dfs(it,vis,adj)) return true; }else if(vis[it] == 1) return true; } vis[num] = 2; return false; } List eventualSafeNodes(int v, List adj){ int vis[] = new int[v]; for(int i=0;i

[@nehathakur40]

Some people make excuses and some make it happen, you are perfect example of working hard even if you achieve hell lot in life .Thank you for inspiring me always and motivating me to push my limits. I really respect the efforts you have put ,in making this video inspite of being unwell.

[@anshusharma11]

Super happy as I was able to solve this myself. I have always been scared of graphs but now it seems to be making sense. Thanks a lot

[@jatinderkaur2030]

Nimce

[@optimus_prime01]

yems@@jatinderkaur2030

[@pooja_SS]

Can we just call this channel The Free University?

[@sumerrawat6947]

Sad that we have to pay huge sums in our shitty universities despite knowing that it is a waste of money and time

[@aeroabrar_31]

and the logo suits too.. TUF (Take U Forward) ~TFU (The Free University) A petition for striver to change the name of the channel..😅😂

[@pranjalck]

Yess bro definitely 😻

[@ujjawalchaurasia5712]

Nope you girls exaggerated everything 😢you Lil kid

[@dheerajkumar824]

No

[@ravi9618]

this is a great approach, although we can reduce use of check array cause we can calculate pathVis[i] == 0 and add them to safeNodes and return them answer will be same

[@Pri.yanka__]

I solved this question without using check array and came back to see your approach and I am so happy that I optimised it. I am not afraid of graphs anymore 😭 Thanks to you.

[@learnwithayush7838]

Nice video sir you are the reason for thousands of smile everyday when we see Accepted in leetcode

[@KunalSinghStatus]

bhaiya audio quality is too good ... wonderful explanation. Thank You ❤❤

[@divyanshpandey3460]

another approach to this problem is to call make a dfs function with return type bool. Inside the function we would create a variable bool b initially assigned to true. This dfs function when called for a starting node would return whether that node is safe or not. This function is implemented using recursion and dfs. Two vectors isSafe and visited are used. Below is the implementation bool dfs(int start,vector &visited,vector adj[],vector &isSafe){ visited[start]=1; bool b=true; for(auto node : adj[start]){ if(!visited[node]){ b=b && (dfs(node,visited,adj,isSafe)); } else{ b=b && isSafe[node]; } } if(b){ isSafe[start]=true; return true; } return false; } vector eventualSafeNodes(int n, vector adj[]) { // code here vector v; vector visited(n,0); vector isSafe(n,false); for(int i=0;i

[@optimus_prime01]

thanks❤

[@anjaligupta5044]

Yup Did it the same way. Was not marking the intermediate safe node true due to which answer was failing. Thanks for putting the solution here :)

[@visase2036]

Thank you for your immense efforts Striver. Here is a solution using single array : visited=[0]*(n) DFS function Call on unvisited nodes : DFS(node): visited[node]=2 #(1+1) 1 for visited and another 1 to denote path for neighbours in graph[node]: if visited[neighbours]==0: if(recurDFS(neighbours)):return True elif visited[neighbours]==2: return True visited[node]=1 //backTracking the visited path Finally whichever nodes are visited only once(1) will be safe nodes and the nodes with 2 are unsafe. safeNodes=[] for nodes in range(n): if visited[nodes]==1: safeNodes.append(nodes) return safeNodes

[@ayushsbhatt6145]

Hey Striver. Great video as always. We appreciate you for making such amazing videos but you need to take care of yourself. We dont want our superstar to fall sick overexerting himself.

[@vaishnavip4808]

I should say this.I have seen numerous videos of yours Tries, Binary trees,Dp and now I have come here to see this.This lecture by far has given me the most amazing concept .My original intuition was towards topological sort, but I never thought about cycle detection usage here.

[@rishabhgupta9846]

understood,solving new problems from the solutions you know is main task

[@zeta_meow_meow]

that whole explanation of all the dfs calls was v.helpfull and good

[@zeta_meow_meow]

code likhe ka tareeka bhi bahut mast tha bhaiyaa 🥰🫶

[@026harshagarwal9]

This is indeed the best example to explain this question

[@sakshamsrivastava6280]

Got a better understanding of the DFS from this.

[@shashanksingh4708]

i reversed the edges and used topo sort , then added each node as it was being processed in the queue

[@shivendrasingh8520]

We can use cycle detection technique and return those edges whose pathvisted is not 1 means excluse cycled edges

[@stith_pragya]

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

[@dank7044]

Did this on my own,all thanks to your last video ka explanation

[@aashiarora3150]

Seeing the eyes of Stiver itz clear, that he might have recorded the video really late at ni8...thanks for the continuous effort bhaiya, Your content really helps

[@lucifergo4332]

aankhon pe nai, code pe dhyaan do

[@piyushacharya7696]

@@lucifergo4332 😂😂😂😂

[@modiji8706]

the whole series like a cake walk

[@NAMAN-wj7dj]

are Modi ji abki baar 400 paar !!

[@AmritprakashShukla]

@@NAMAN-wj7dj 😂😂

[@rajsekhardutta8891]

Understood! Great explanation as always. 🤩❤‍🔥

[@RajeevCanDev]

From this problem we can get that how google map finds out our destination and also how it manages different paths for the same destination and finds out the best possible path by the shortest path algorithm(path with less number of edge weight(basically the traffic and distance)) THIS IS WAY COOLER AND AMAZING THAN IT REALLY SEEMS TO BE ;-)

[@deepakjain4481]

no that ain''t true because we can see that it fail over loops there can be a path emerging from the loop but it will ignore it

[@ankishkhandelwal1061]

while Doing Dry run found out we actually don't need check array because the path array is not marked to 0 when cycle is found and all the node is cycle path is also not unmarked and for a node who is connected to a cycle will not unmark also Great Explanation 😀😀😀

[@priyanshkumar17]

Yes. We may use : for(int i = 0; i < V; i++) { if(!pathVis[i]) safeNodes.push_back(i); }

[@vatsalvasoya5243]

Understood!! Very well explained!!!

[@MMNayem-dq4kd]

Understood,very well explained.💕💕

[@tasneemayham974]

BESTTTT TEACHHHEERRR EVERRR!!!! THANKKK YOUUU STRIVERR!!

[@komalkrishna7836]

Understood!! Great explanation

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@venumsingh]

Thanks for the video. xor of vis and pathVis seem to give the correct answer. no need check array.

[@pulkitchausali1354]

solve this problem myself without watching video that's striver magic explanation

[@kalravsharma178]

Thanks for the quality content!!

[@CodeMode9313]

Thanks ...tum accha kaam karta hai habibi

[@dojoPojo]

We can just add safenodes in dfs after visiting all neighbours of it and not ending in cycle so no need to do traversal again c++ code : class Solution { public: /* find all the nodes that are not part of the cycle directed so path vis and vis */ bool hascycle(int src, vector& graph, vector&vis, vector&pathvis, vector&safenodes) { vis[src]=true; pathvis[src]=true; for(auto it:graph[src]) { if(!vis[it]) { if(hascycle(it,graph,vis,pathvis,safenodes)) return true; } if(pathvis[it]) { return true; } } pathvis[src]=false; safenodes.push_back(src); return false; } vector eventualSafeNodes(vector& graph) { int n = graph.size(); vectorvis(n,false); vectorpathvis(n,false); vectorsafenodes; for(int i=0; i

[@preetisahani5054]

Awesome explanation

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@ravisingh-el8np]

thanks striver i could code it myself

[@cinime]

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

[@saisriangajala8399]

In undirected graph only components with single node will be safe nodes..

[@OnstreamGaming]

amazing teacher

[@_hulk748]

Understood sir thankyou and take care sir❤🙇‍♂🙏

[@atheisttttt]

Saw recent racism incident in Warsaw (Polland) against Indians - take care bro !

[@ideas4951]

Bhaiya aap mast padhate ho ❤

[@sarthaksharma9322]

As always an amazing video Striver, just a small question though, instead of keeping a safeNodes and check array, if we are done with the for loop, can't we just directly push the node into the safeNodes array at that point only, I guess if we do this, then we won't require another for loop whose only job is to then read from the check array and push into the safeNodes array.

[@k.k.harjeeth5422]

even that extra for loop is also not required , just call dfs(i) for all values of i even if the node is already visited , if dfs(i) is False ,(as dfs returns if cycle is present) then add i to the answer. class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: n=len(graph) visited=[0]*n pathVisited=[0]*n answer=[] def dfs(node): visited[node]=1 pathVisited[node]=1 for i in graph[node]: if(not visited[i]): if(dfs(i)): return True elif(visited[i] and pathVisited[i]): return True pathVisited[node]=0 return False for i in range(len(graph)): if(not dfs(i)): answer.append(i) return answer

[@himalayadebbarma-we4pt]

Understood!!

[@shyren_more]

Understood, maja aagaya

[@heichou7334]

Really helpful but would love if you explain the code little bit.

[@jambajuice07]

almost halfway done !

[@242deepak]

I think you haven't covered cycle detection in directed graph in any of your previous videos in this series.

[@antassachan1782]

exactly

[@aeroabrar_31]

@@antassachan1782 It's the 56th video of the playlist go and check it once.

[@aeroabrar_31]

It's the 56th video of the playlist go and check it once.

[@s.s.lingeshkumar865]

understood a lot anna❤

[@chandrachurmukherjeejucse5816]

Understood. Done this in a bit different way. I have an array isSafe which indicates if a node is safe or not or not visited. an array isVisited which keeps track of path visited nodes. if any node's dfs encounters a node that is already path visited we mark it as unsafe(as cycle is there) call dfs for all nodes if all the paths leads to an node that is marked safe then we mark that as safe and even if one of them encounters an node that is not safe we mark it as unsafe. class Solution { private: bool checkIfSafe( int ind, vector &graph, vector &isVisited, vector &isSafe) { if(isVisited[ind]) return isSafe[ind] = false; if(isSafe[ind] != -1) return isSafe[ind]; bool res = true; isVisited[ind] = true; for(int &node : graph[ind]) { res = res && checkIfSafe(node, graph, isVisited, isSafe); } isVisited[ind] = false; return isSafe[ind] = res; } public: vector eventualSafeNodes(vector& graph) { int n = graph.size(); vector res; vector isSafe(n, -1); vector isVisited(n, false); for(int i = 0; i < n; i++) { if(isSafe[i] == -1) { checkIfSafe(i, graph, isVisited, isSafe); } if(isSafe[i] == 1) { res.push_back(i); } } return res; } };

[@suheabkhan2546]

Understood very well explained

[@supratimbhattacharjee5324]

We don't need the check array, the pathVis array will do the work of finding safe nodes.

[@ssv6055]

Aye aye captain ! 💪🏻

[@original_gangsta_]

Understood

[@pratik.784]

Best channel

[@pragatigupta7123]

Full Understood 😃

[@mriduljain6809]

Understood Bhaiya

[@aniruddhadas1778]

Instead of using another check array we could easily find the safe states using pathvis only. if(pathvis[i]==0) { ans.add(i); }

[@surajkumar-ci4qr]

Yeah we can do that

[@jacksparrow50]

In the main function, in the for loop, we have used the dfsCheck function, which is supposed to return a boolean value. But here it is not stored anywhere and thus will throw an error.

[@proton3773]

What an explanation!!

[@spydycoder6668]

understood bhaiya

[@thinkingmad1685]

Happy teachers day bhaiyya 🙏

[@dinanathmandal3371]

understood sirji

[@KratosProton]

Great explaination

[@UECAshutoshKumar]

Thank you sir

[@udayjordan4262]

you can simply use the path visited array no need for the check array ...as if there is no return call made all those are my part of cycle or leading to cycle

[@sunilsinghrathore7825]

can it be done by this approach?->in cycle detection algorithm using dfs,whenever we are returning true in dfs function(means a cycle is detected)store that node in a data structure and in the end all the nodes which were either a part of cycle or connected to cycle will get stored in that structure,all the remaining nodes which are not there in that data structure will be safe nodes.

[@najimali32]

Thanks for the explanations. You actually dont need checkNode array. PathVis will return our desired output. use this - if(pathVis[i] == false) safeNodes.add(i);

[@AditiAgarwal-rw3lq]

great video

[@bro_code3505]

hello striver bhaiya I hope you will consider this to be a useful comment because as you told in starting that we are going to use cycle detection technique in this problem and despite of this if we could know why to use cycle detection might create a crave of learning graph more enough. (Understood).

[@fmkhandwala39]

i know you asked striver, but just wanted to help anyway i could. i am assuming you are asking for the intuition behind using, the cycle detection method. now if you observe the questions, it asks us to find all the safeNodes(whose paths end up at a terminalNode.) A safeNode is a node, which has "every" (emphasize on every) path ending at terminal. now if this node was part of a cycle, it can never have all of its path ending at terminal node!

[@rameshbabuy9254]

please create series on string problems

[@parshchoradia9909]

Understood Sir!

[@lakeshkumar1252]

quality content 😍

[@adityasaxena6971]

Understood 💯💯

[@fmkhandwala39]

understood!!!!

[@kunalbhika6424]

Understood🤩

[@kirtitung4877]

understood!!! Thankyou sir !!!

[@Ankit.yt_885]

Very good! Thanks :)

[@HarshSingh-qq2jf]

If a node touches a NOT safe node in a path, it means because of that path the node also becomes NOT safe Function to check if the node is safe or not, returns false throughout the path whenever a NOT safe node is encountered in the path ( NOT safe because a cycle is found in the path) safe[ ] array instead of vis[ ] array safe[ ] = 0 means unvisited safe[ ] = -1 means NOT safe safe[ ] = 1 means safe If adjacency List is empty for a node, it means a terminal node is encountered which returns true class Solution { private: bool isSafe(int source, vector adj[], vector &safe, vector &vec) { safe[source] = -1; for(auto v:adj[source]) { if(!safe[v]) { if(isSafe(v, adj, safe, vec)) { safe[v] = 1; vec.push_back(v); } else return false; } else if(safe[v] == -1) return false; } return true; } public: vector eventualSafeNodes(int V, vector adj[]) { vector vec; vector safe(V, 0); for(int i = 0; i < V; i++) if(!safe[i]) { if(isSafe(i, adj, safe, vec)) { safe[i] = 1; vec.push_back(i); } } sort(vec.begin(), vec.end()); return vec; } };

[@saikrishna872]

UNDERSTOOD

[@studynewthings1727]

Understood.

[@atharvadeshmukh6328]

Understood!

[@Gothamcoming]

at end of detect cycle before returning false simply push node in output array below implementation- bool detectcycleforstate(vector input,int st,vector &visited, vector &pathvisited,vector &output){ pathvisited[st]=1; visited[st]=1; for(int v : input[st]){ if(!visited[v]){ if(detectcycleforstate(input,v,visited,pathvisited,output)){ return true; } } else if(pathvisited[v] && visited[v]){ //obvious it is visited i write only for // understanding return true; } } pathvisited[st]=0; output.push_back(st); return false; } vector eventualsafestate(vector input){ int n=input.size(); vector safestate; vector pathvisited(n,0); vector visited(n,0); for(int i=0;i

[@suryakiran2970]

Understood❤

[@The_Shubham_Soni]

UNDERSTOOD.

[@Learnprogramming-q7f]

Thank you bhaiya

[@Rajat_maurya]

Without check array class Solution { private: bool dfs(int node,vector &vis,vector &pathvis,vector adj[]) { vis[node]=1; pathvis[node]=1; for(auto it:adj[node]) { if(vis[it]==0) { if(dfs(it,vis,pathvis,adj)==false) { return false; } } else if(pathvis[it]==1) { return false; } } pathvis[node]=0; return true; } public: vector eventualSafeNodes(int n, vector adj[]) { vector vis(n,0),pathvis(n,0); vector ans; for(int i=0;i

[@ashishgoyal6527]

💯

[@shrutisaxena2111]

Hey which tool do you use in your iPad for explanation?

[@-VLaharika]

Understood 👍

[@aastikofficial6100]

We dont need any extra check vector we can simply modify the path and optimise it

[@prudhvirajmacherla9854]

finding somewhat hard this video until the graph playlist

[@surajpadihar5027]

Understood 🙌

[@priyanshvatsal9791]

Understood 😇

[@cypher7536]

understood! ❤❤❤❤❤❤❤❤

[@m.r.b.e.a.s]

“understood”😀