G-20. Find Eventual Safe States - DFS
Вставка
- Опубліковано 6 лип 2024
- GfG-Problem Link: bit.ly/3C90n59
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
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.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/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
Your dfs cycle explanation is good enough. That one video does the charm of other questions.
this man will be remembered for so long for his work
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
Makes sense! The check array was added to increase the understanding :) Good to see such comments 💯
@@takeUforward Thanks for the quality content! :D
Then this question will boil down to checking only the "false" pathVis nodes. Nice!
@@rishavsaha5254 Exactly
*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
Can we just call this channel The Free University?
Sad that we have to pay huge sums in our shitty universities despite knowing that it is a waste of money and time
and the logo suits too..
TUF (Take U Forward) ~TFU (The Free University)
A petition for striver to change the name of the channel..😅😂
Yess bro definitely 😻
Nope you girls exaggerated everything 😢you Lil kid
No
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.
Understood! Great explanation as always. 🤩❤🔥
This is indeed the best example to explain this question
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
Nimce
yems@@jatinderkaur2030
Nice video sir you are the reason for thousands of smile everyday when we see Accepted in leetcode
Got a better understanding of the DFS from this.
understood,solving new problems from the solutions you know is main task
bhaiya audio quality is too good ... wonderful explanation. Thank You ❤❤
Understood!! Very well explained!!!
Thanks for the quality content!!
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
Understood!! Great explanation
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.
Thank you very much. You are a genius.
Understood,very well explained.💕💕
Understood very well explained
that whole explanation of all the dfs calls was v.helpfull and good
code likhe ka tareeka bhi bahut mast tha bhaiyaa 🥰🫶
Thank you, Striver 🙂
i reversed the edges and used topo sort , then added each node as it was being processed in the queue
Great explaination
BESTTTT TEACHHHEERRR EVERRR!!!! THANKKK YOUUU STRIVERR!!
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
Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
the whole series like a cake walk
are Modi ji abki baar 400 paar !!
Did this on my own,all thanks to your last video ka explanation
Awesome explanation
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
thanks❤
understood a lot anna❤
understood!!!
Thankyou sir !!!
Hey which tool do you use in your iPad for explanation?
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.
In undirected graph only components with single node will be safe nodes..
What an explanation!!
Very good! Thanks :)
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.
Thanks ...tum accha kaam karta hai habibi
Understood sir thankyou and take care sir❤🙇♂🙏
Saw recent racism incident in Warsaw (Polland) against Indians - take care bro !
can anyone suggest any other intuition for solving this question apart from cycle method??
Aye aye captain ! 💪🏻
thanks striver i could code it myself
understood! ❤❤❤❤❤❤❤❤
Hey striver,
If we consider a graph like 0->1->2 then it is giving 0,1,2 as safe nodes
But if we look at path from 0 to 1, it doesn't end in a terminal node since 1 is not an terminal node. So my doubt is why 0 is considered as safe node??
Thank you sir
understood!!!!
Understood! Super cool explanation as always, thank you very much!!
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
aankhon pe nai, code pe dhyaan do
@@lucifergo4332 😂😂😂😂
We can use cycle detection technique and return those edges whose pathvisted is not 1 means excluse cycled edges
Understood, maja aagaya
i have a question. pathvisited just takes care the fact whether the function call has finished or not. so shouldn't do pathvisited[node]=0 before we return anything for that function?
Full Understood 😃
Understood Sir!
Understood 💯💯
Thanks for the video. xor of vis and pathVis seem to give the correct answer. no need check array.
Understood 🙌
Best channel
almost halfway done !
Bhaiya aap mast padhate ho ❤
great video
leetcode link: leetcode.com/problems/find-eventual-safe-states/
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.
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.
understood!
Understood ❤
quality content 😍
Thank you bhaiya
Understood 👍
Understood!!
Understood 😀
Happy teachers day bhaiyya 🙏
Can some please tell me which Cycle detection video he's referring to @ 16:24 . Because the Cycle detection video in this series in for undirected graph.
Directed graph one
UNDERSTOOD.
Understood bhaiya
amazing explanation
understood sirji
Understood❤
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
understood bhaiya
“understood”😀
understood
Understood
please create series on string problems
Understood!
Understood 😇
understood!!!!!!!!!
Understood Bhaiya
Instead of using another check array we could easily find the safe states using pathvis only.
if(pathvis[i]==0)
{
ans.add(i);
}
Yeah we can do that
Understood.
understood✌🤟
understood.
but we can solve this without cycle detection as well, by assuming that each node is a component.
Really helpful but would love if you explain the code little bit.
UNDERSTOOD
understood💙💚💙
is it not possible? we just find out node in the in the adjacency list which has an empty list, which means that is the safe node. and then find out which all nodes' list contains only that safe node so that those nodes will also be safe nodes.
I think you haven't covered cycle detection in directed graph in any of your previous videos in this series.
exactly
@@antassachan1782 It's the 56th video of the playlist go and check it once.
It's the 56th video of the playlist go and check it once.