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
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
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.
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
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.
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){
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
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.
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.
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
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 😀😀😀
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
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
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 ;-)
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
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; } };
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.
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
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; } };
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);
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 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.
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).
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!
My thought--- i added a terminal nodes in a list,,,---- added a dfs for each node ,check cycle if passes --- check if contains terminal nodes if passes then add it to our answer----** I used terminal nodes as I want to know when it going 2 end
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.
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
this man will be remembered for so long for his work
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.
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
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
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.
Nice video sir you are the reason for thousands of smile everyday when we see Accepted in leetcode
bhaiya audio quality is too good ... wonderful explanation. Thank You ❤❤
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❤
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 :)
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
i reversed the edges and used topo sort , then added each node as it was being processed in the queue
We can use cycle detection technique and return those edges whose pathvisted is not 1 means excluse cycled edges
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
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.
understood,solving new problems from the solutions you know is main task
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.
This is indeed the best example to explain this question
Got a better understanding of the DFS from this.
that whole explanation of all the dfs calls was v.helpfull and good
code likhe ka tareeka bhi bahut mast tha bhaiyaa 🥰🫶
Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood! Great explanation as always. 🤩❤🔥
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 😂😂😂😂
Did this on my own,all thanks to your last video ka explanation
Understood,very well explained.💕💕
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 😀😀😀
Yes. We may use :
for(int i = 0; i < V; i++) {
if(!pathVis[i]) safeNodes.push_back(i);
}
Understood!! Very well explained!!!
Thanks ...tum accha kaam karta hai habibi
Thanks for the video. xor of vis and pathVis seem to give the correct answer. no need check array.
Thank you very much. You are a genius.
the whole series like a cake walk
are Modi ji abki baar 400 paar !!
@@NAMAN-wj7dj 😂😂
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
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
Awesome explanation
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 ;-)
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
Bhaiya aap mast padhate ho ❤
Understood!! Great explanation
In undirected graph only components with single node will be safe nodes..
Understood sir thankyou and take care sir❤🙇♂🙏
Understood very well explained
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
Thank you, Striver 🙂
BESTTTT TEACHHHEERRR EVERRR!!!! THANKKK YOUUU STRIVERR!!
thanks striver i could code it myself
amazing teacher
solve this problem myself without watching video that's striver magic explanation
Thanks for the quality content!!
understood a lot anna❤
Happy teachers day bhaiyya 🙏
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;
}
};
Understood! Super cool explanation as always, thank you very much!!
Great explaination
We don't need the check array, the pathVis array will do the work of finding safe nodes.
Full Understood 😃
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.
Really helpful but would love if you explain the code little bit.
almost halfway done !
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
Best channel
What an explanation!!
Understood Sir!
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;
}
};
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);
understood bhaiya
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
💯
understood sirji
Understood bhaiya
Understood, maja aagaya
Understood!!
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 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.
Thank you sir
Understood 💯💯
Thank you bhaiya
Understood.
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).
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!
We dont need any extra check vector we can simply modify the path and optimise it
Aye aye captain ! 💪🏻
Saw recent racism incident in Warsaw (Polland) against Indians - take care bro !
understood!!!
Thankyou sir !!!
UNDERSTOOD.
amazing explanation
My thought--- i added a terminal nodes in a list,,,---- added a dfs for each node ,check cycle if passes --- check if contains terminal nodes if passes then add it to our answer----** I used terminal nodes as I want to know when it going 2 end
A simpler code using just two arrays
class Solution {
public:
bool dfs(int node, vector adj[],vector &visited)
{
visited[node]=1;
for(auto x: adj[node])
{
if(visited[x]==1)
return false;
else if(dfs(x,adj,visited)==false)
return false;
}
visited[node]=0;
return true;
}
vector eventualSafeNodes(int V, vector adj[]) {
vector ans;
vector visited(V,0);
for(int i=0;i
UNDERSTOOD
Understood 👍
Understood!
Understood🤩
great video
Understood 🙌
Understood❤
quality content 😍
please create series on string problems
“understood”😀
Understood 😇
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.
understood!!!!
Very good! Thanks :)
Understood 😀
understood! ❤❤❤❤❤❤❤❤