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.
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.
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 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.
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 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
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){
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
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 ;-)
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 😀😀😀
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.
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.
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.
well yes i understood how detect a cycle in a directed graph but also true that i havent understood this code (logic was ez but i was unable to implement this) lets hope i get it soon
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
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; } };
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; } };
If we take the check array by reference,then do we need to initialise check if node to zero in code.because we have already initialised it with 0,just we back track we mark the node as 1.please tell me if I am right
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?
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
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
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.
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);
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??
we have already declared a {0} wala array. Why do we need those check[i]=0 inside all. Once the the loop gets over the check[node]=1 is alone sufficient. Can someone please explain ??
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 can eliminate check[ ] array by doing some modifiications, class Solution { public: bool checkdfs(int node,vector adj[],int vis[],int pathvis[],vector &temp){ vis[node] = 1; pathvis[node] = 1; temp.push_back(node); for(auto neigh : adj[node]){ if(!vis[neigh]){ if(checkdfs(neigh,adj,vis,pathvis,temp)){ //we are not back tracking the path array return true; } } else if(pathvis[neigh]){ //we are not back tracking the path array return true; } } // the cycle is not presant back track the path array pathvis[node] = 0; return false; } vector eventualSafeNodes(int V, vector adj[]) { // code here int vis[V] ={0}; int pathvis[V] = {0}; sets; vector ans; for(int i=0;i
it will also work without using a check array question must be how? then when you are getting a cycle you are coming out of the function without having the path flipped so every node in the cycle will now be path visited later you go for the next unvisited node and if you encounter a visited node you check if it is path visited or not if path visited then means it is previously be the part of any cycle so you again return true and didnt change the current node path visited what if you go for the safe node it the recursive call will return false also previously marking them false hence all the nodes having the path visited equals 0 will be your safe node
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
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.
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.
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
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
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 ❤❤
This is indeed the best example to explain this question
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.
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 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
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 :)
thanks for this solution bro I was also trying the same approach but it didn't worked , your solution really helped me
that whole explanation of all the dfs calls was v.helpfull and good
code likhe ka tareeka bhi bahut mast tha bhaiyaa 🥰🫶
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 😂😂😂😂
Got a better understanding of the DFS from this.
understood,solving new problems from the solutions you know is main task
Striver Bro now I am enjoying DSA bro Thank you
We can use cycle detection technique and return those edges whose pathvisted is not 1 means excluse cycled edges
i reversed the edges and used topo sort , then added each node as it was being processed in the queue
Did this on my own,all thanks to your last video ka explanation
Understood! Great explanation as always. 🤩❤🔥
the whole series like a cake walk
are Modi ji abki baar 400 paar !!
@@NAMAN-wj7dj 😂😂
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 ;-)
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
Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood!! Very well explained!!!
solve this problem myself without watching video that's striver magic explanation
BESTTTT TEACHHHEERRR EVERRR!!!! THANKKK YOUUU STRIVERR!!
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);
}
20:48 do we really need this line? I'm not able to find any reason. I'm to submit all the TC's without this line. Can anyone help me with this query?
Because it is already initialised with 0
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.
Thanks ...tum accha kaam karta hai habibi
In undirected graph only components with single node will be safe nodes..
Understood,very well explained.💕💕
Understood!! Great explanation
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
Bhaiya aap mast padhate ho ❤
Thanks for the quality content!!
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
💯
Thank you very much. You are a genius.
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.
Thanks for the video. xor of vis and pathVis seem to give the correct answer. no need check array.
well yes i understood how detect a cycle in a directed graph
but also true that i havent understood this code (logic was ez but i was unable to implement this)
lets hope i get it soon
Understood! Super cool explanation as always, thank you very much!!
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.
Saw recent racism incident in Warsaw (Polland) against Indians - take care bro !
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
leetcode link: leetcode.com/problems/find-eventual-safe-states/
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;
}
};
Understood, maja aagaya
Happy teachers day bhaiyya 🙏
Thank you, Striver 🙂
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 sir thankyou and take care sir❤🙇♂🙏
thanks striver i could code it myself
We don't need the check array, the pathVis array will do the work of finding safe nodes.
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;
}
};
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
Awesome explanation
If we take the check array by reference,then do we need to initialise check if node to zero in code.because we have already initialised it with 0,just we back track we mark the node as 1.please tell me if I am right
understood a lot anna❤
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?
Really helpful but would love if you explain the code little bit.
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
The funny part is that every time you click on the keyboard it feels like someone is knocking on my door, so I opened my door and asked who was there.
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.
Aye aye captain ! 💪🏻
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
Getting TLE when I solve the same problem in Leetcode. What could be the reason?
same here, not able to pass all testcases on GFG
amazing teacher
Full Understood 😃
Best channel
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.
Hey which tool do you use in your iPad for explanation?
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);
In leetcode this approach is giving TLE??
We dont need any extra check vector we can simply modify the path and optimise it
can anyone suggest any other intuition for solving this question apart from cycle method??
please create series on string problems
“understood”😀
almost halfway done !
quality content 😍
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??
What an explanation!!
but we can solve this without cycle detection as well, by assuming that each node is a component.
we have already declared a {0} wala array. Why do we need those check[i]=0 inside all. Once the the loop gets over the check[node]=1 is alone sufficient.
Can someone please explain ??
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!
Great explaination
finding somewhat hard this video until the graph playlist
Understood 💯💯
we can eliminate check[ ] array by doing some modifiications,
class Solution {
public:
bool checkdfs(int node,vector adj[],int vis[],int pathvis[],vector &temp){
vis[node] = 1;
pathvis[node] = 1;
temp.push_back(node);
for(auto neigh : adj[node]){
if(!vis[neigh]){
if(checkdfs(neigh,adj,vis,pathvis,temp)){
//we are not back tracking the path array
return true;
}
}
else if(pathvis[neigh]){
//we are not back tracking the path array
return true;
}
}
// the cycle is not presant back track the path array
pathvis[node] = 0;
return false;
}
vector eventualSafeNodes(int V, vector adj[]) {
// code here
int vis[V] ={0};
int pathvis[V] = {0};
sets;
vector ans;
for(int i=0;i
it will also work without using a check array question must be how?
then when you are getting a cycle you are coming out of the function without having the path flipped so every node in the cycle will now be path visited
later you go for the next unvisited node and if you encounter a visited node you check if it is path visited or not if path visited then means it is previously be the part of any cycle so you again return true and didnt change the current node path visited
what if you go for the safe node it the recursive call will return false also previously marking them false hence all the nodes having the path visited equals 0 will be your safe node
with pathVis array we can decide i think no need of check array for that
understood!!!
Thankyou sir !!!
*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
Very good! Thanks :)