G-25. Find Eventual Safe States - BFS - Topological Sort
Вставка
- Опубліковано 4 вер 2022
- 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
understood
Understood
Initially the terminal nodes are those who have outdegree 0
but after reversal the terminal nodes becomes those which have indegree 0
so we can apply Kahn's algo to find all the nodes connected to it which have linear dependency on the terminal node or is on the path which leads to terminal node
so if the nodes is a part of a cycle or points to a cycle , that path cannot lead to terminal node as each node in that path will have cyclic dependency
thanks that helps!!
the inttution behind making the reverse graph is to make indgree 0 for terminal nodes which will definitely be safe. stating node with indgree 0 may or may not lead to terminal node,they can lead to cycle. hence we have reversed the graph to play safe by making indgree of termial node 0 and reversing the graph
👍 thanks
Understood! Such a great explanation as always, thank you very much!!
Absolutely better explanation ever i have seen...
Thank for this graph series...I can say no corner is cut in this course.
Understood !
Was able to do on my own after your approach thanks.🙃
Understood🔥...You made every topic easier, thank you so much sir
Another way of looking at this - Starting from the terminal node (indegree = 0), we will only be able to bring the other node'ss (say X) indegree to 0 if there is no connection of X with a non-safe node.
For example - 8 is a node whose indegree cannot be brought down to 0 as it is connected to a non-terminal node.
Hence we can conclude that all nodes whose indegree is 0 after the traversal starting from terminal node, all such nodes are safe.
Thank you, Striver 🙂
understood such a great explanation bhayiyaa...
I thought of trying a new approach. I initialized and stored outdegree in an array and added the nodes with outdegree 0 to the queue and ran a while loop, in which I eliminate the element with outdegree 0 and added to the safe state list. and reduced the outdegree by 1 of all nodes which points to the initial node. Although this method works fine but it has more time complexity.
Habibi ye toh hum khud solve kar di ...vakai tum aacha padati ..cambridge me apply karke dekhti tutor post ke liye . Understoos
😆
understood. I have written the code after getting the intuition in the middle of the video. I coded successfully in python I got the TLE. And again I started continue watching the video, in that I got surprised how you merged two for loops into one for loop. I applied that and it got submitted successfully. Thankyou 🙂
Great explaination
Understood Sir, Thank you very much
AMAAAZZINGGG STRIVVEERRR!!
Understood bhaiya 🔥
Understood Bhaiya!!
Understood! Thank you
Thank you bro!!
Understood Sir!
Thank u bhaiya❤️
Thank you sir 😁
Understood
Thank You Striver bhaiya u are doing a great job!!
Striver Bhaiya, can you please discuss problem C and D of Weekly and Biweekly Leetcode Contests.
It would be a great help 🙏🙏🙏
Bhaiyaa, thank you so much for graph series, per bhaiya please can you also make series on segement trees, tried learning from so many places, but nowhere satisfactory content is found, bana do na bhaiya ek series please
UNDERSTOOD.
We can also do by using the algo which we have used in cycle detection in directed graph instead of returning when cycle was found just continue to do and after all the nodes are visited then add the nodes which are not pathvisited
understood 🔥
Thank you bhaiya
Understood❤
Understood!
00:06 Find the safe nodes in a directed graph
02:20 The safe notes in the given graph are 2, 4, 5, and 6
04:29 Reverse the graph and perform topological sort
06:40 Identifying terminal nodes and performing BFS for topological sorting of a reversed graph
08:42 Reduce the in degree to one and remove the node
10:41 Implementing topological sort on a graph
12:51 Convert i t to I and count in degrees for adjacency nodes
15:08 The integrity was zero, which caused the code to be shorter and simpler.
Crafted by Merlin AI.
understood!
Understood!!!
understood!!
A better approach according to complexity is using dfs and checking for cycle if cycle is present its not safe and if safe we push it to ans.
understood
Understood.
Understood
understood💙🧡💙
Understood:)
Understood++ bro
THANKS ALOT STRIVER FOR THIS APPROACH.
I have tried solving it in DFS fashion. with TC=O(N), without reversing and sorting.
very simple Intution of just traversing a every node if it leads to non terminal nodes return false, else true. AND FINALLY every node with true value is safe NODE.
As we are traversing the same node again and again , i have memoized it.
class Solution {
public:
int dfs(int i,vector &visited,vector &pvis,vector &dp,vector& graph)
{
if(dp[i]!=-1)
return dp[i];
int temp=1;
visited[i]=1;
pvis[i]=1;
for(auto it:graph[i])
{
if(pvis[it]==0)
temp=dfs(it,visited,pvis,dp,graph);
else
temp=0;
if(temp==0)
{
break;
}
}
pvis[i]=0;
return dp[i]=temp;
}
vector eventualSafeNodes(vector& graph) {
int n=graph.size();
vector visited (n,0);
vector pvisited (n,0);
vector dp (n,-1);
int temp;
for(int i=0;i
at 11:04 why 11 is not a safe node , as it itself is a terminal node?
11 is not a terminal node. You are seeing the graph after reversal of edges at 11:04
Look at the graph initially.
IDK every time I will forget the core logic for this problem, like to see the cycle if found ignore the related node, Just wrote for my refe...!🤣🤣
Thanks for the video
love you
Hey, really like your videos. Extremely helpful. Can you please use smaller screen for facecam? Like small square on the bottom-right side instead of full screen?
No bro this is perfect
@@anvesh5377 it's kinda hard focussing when you're studying in laptop. As the screen is already small.
No it's perfect 👍
Thank you bhaiya .. understood.. new course kb se start hoga ?
Simple way to solve using outdegree array instead of reversing stuff
class Solution {
public:
vector eventualSafeNodes(vector& graph) {
int V = graph.size();
vector outdegree(V,0);
vector adj[V];
findList(graph,outdegree,adj);
//list and outdegree are ready
queue q;
vector ans;
for(int i=0;i
Can anyone explain why we are using topological sort for solving this problem 😅 ?
done🙂
understood🤓
understooodddddddddd
the algorithm was beautiful
UnderStood❤
"understood"
Different approach 😀
I have tried topological sort but creating an array of out-degree (without reversing the graph).
class Solution {
List eventualSafeNodes(int V, List adj) {
// Your code here
int[] outdegree = new int[V];
Queue queue = new LinkedList();
List topo = new ArrayList(V);
HashMap map = new HashMap();
for(int i=0; i
bro, I think you are creating graph with reversed edges.
Please check 3rd line below here, its a reverse edge case
for(int i=0; i
@@srinish1993 Yes, i thought the same...
11 is also safe node cause it's itself terminal node 11:19
Could you please explain the intuition behind coming to the conclusion that this is toposort problem. I made a hypothesis that all nodes that are part of a cycle or entering to a unsafe node are unsafe and solved it as an extention to cycle detection problem. That hypothesis solved the problem but I don't know how to prove it. does this mean that after the end of kahn's algo all nodes that are left with in degree not equal to zero are part of a cycle or enter a cycle ?
understood :-)
Bhaiya aap ki t-shirt take u forward wali bahut jyada attract karta mtlb bahut jyada pasand kaise mil sakta hai bhiya
Hi, how come we did not check for cycles via a visited array? how does it automatically get excluded from the queue?
if we add only those node whose indegree is 0 then we don't need to sort
TC= O(v+e) + vlog(v) ->>>>improved to -> O(v+e)
SC = O(v)
Look think this way which nodes all path will be go to terminal nodes ? Only if there is no cycle in all the path right ! So let take an exp. -> 1 -> 2 -> 3 ->4 -> 5 -> 6, here only 5 and 6 are safe nodes, So which all comes after that cycle(2->3->2). So if
\ /
traverse from 1 then 2 then it meets a cycle and q becomes empty. But if we somehow start traversing from 5(after cycle), it will definately go to a terminal nodes. But how will u find the starting node after a cycle, instead we can go from 6 to 5 in reversed way, thats why we r reversing the edges of the graph so that inseatd of starting from 1(inDegree = 0), we can start from 6(now, indegree = 0 i.e prev, outDegree= 0 i.e a terminal nodes.)
If we reverse the direction between 8 and 10 then it's not a cycle and if we try to solve the question..... Then I think it won't work......is there any rule how many incoming or outgoing edges a node can have.... Someone please explain this.
self note :
why we need to reverse nodes in bfs and not dfs:
because in dfs when ever we find a node which is part of a cycle we keep returning true and keeping adding nodes utiill we are back to the orignal node which this call. hence we have a complete list of nodes which eventually lead to or are a part of a cycle.
now in bfs , at 8:03 see if we dont reverse the edges then 11 gets added to safe sequence which is wrong, now if we reverse the edges, the edges which are not a part of a cycle or dont lead to cycle still do the same, but in reverse direction (hence they will still be a part of safe sequence) , but nodes like 11 which lead to a cycle earlier ,now wont get added since we are doing a topological ordering on this reversed graph and its degree will never be zero
Can't we do it without reversing but only storing the inDegree frequency? If we do like that where do we fail? I am unable ot figure it out.
Why we have to reverse the Graph?? What was logic behind it?
How does 1 come to the answer its one path is leading to the cycle and according to the question the terminal nodes do not have outgoing edges ?
@takeuforward, what if i dont reverse?
indegree or outdegree
🎉🎉❤
US
You have'nt told the reason why you have reversed the edges in graph, the main reason to do this I guess is because if you do topo sort using BFS, you will get outside nodes attached to cycle because their indegree will become zero, but they are not safe states because they are attached to cycle.
to solve this problem, you reversed the edges, to make sure every node outside cycle has an indegree 1, which can't be a part of toposort, and eventually when you reverse edges (cycle remains same) and even terminal nodes wont get affected.
I told it, please watch the entire video. I have told it, we wanna start from the terminal nodes, as the question states who end at terminal nodes. So we start at terminal nodes.
@@takeUforward correct me if i am wrong but is reversing required? can't we apply the same concept but for outdegrees? find all nodes with outdegrees 0 and add to q. at each level dec the outdegree of neighboring nodes?
@@brucebatmanwayne8514 Ultimately you will be also doing the same thing, because you have to create reverse adjacency list to traverse, if you dont do it and push all elements whose outdergree is zero into queue then how will you reach to its adjacent nodes because no one has outgoing edges.
Awesome bro..i also came to this logic by giving some thought..but when it struck it was like a high..rarely experienced!
Amazing... Thanks for such answer
"UNDERSTOOD"
"Understood"
Hey Striver, i have a doubt here. In Video G-20 we solved this problem simply by modifying cycle detection and got T.C = O(N) +O(N+E) and in this method we got T.C.= O(N+E) + O(N*logN) so if i am not wrong the previous time complexity is more optimized than this one but i got TLE on leetcode on G-20 method but G-25 method worked properly. Don't why this opposite behaviour?? Please tell me.. BTW loved this graph series..
*I am attaching both the code:*
*G-20 method (passed 102/112 testcase)( T.C = O(N) +O(N+E))*
class Solution {
private:
bool usingdfs(int src, vector &vis, vector &pathvis, vector graph, vector &ans){
vis[src]=1;
pathvis[src]=1;
for(auto x: graph[src]){
if(!vis[x]){
if(usingdfs(x, vis, pathvis, graph, ans)==true) return true;
} else if(pathvis[x]==1){
return true;
}
}
pathvis[src]=0;
return false;
}
public:
vector eventualSafeNodes(vector& graph) {
int n=graph.size();
vector vis(n, 0);
vector pathvis(n, 0);
vector ans;
for(int i=0; i
@@anmolgarg2951 My Code of DFS from lecture G-20 got ACCEPTED and its RunTime is less then the RunTime of Kahn's algo 😂😂 ... obviously toposort is more optimised
code ->
class Solution {
public:
bool dfs(int S, vector &vis, vector &path, vector &adj){
vis[S] = path[S] = 1;
for(auto &it: adj[S]){
if(!vis[it]){
if(dfs(it, vis, path, adj)) return 1;
}
else if(path[it]) return 1;
}
path[S] = 0;
return 0;
}
vector DoDfs(int n, vector &adj){
vector vis(n, 0), path(n, 0);
for(int i=0; i
@@anmolgarg2951 remove if(!visited[]) from eventual safe node function
I think its because we are using DFS in the first method and DFS reaches to the terminal node in less time as compared to the BFS which is used in the method 2. It depends on the size of input.
how can i think of such solutions by myself...im doing ur sheet but have to watch solutions of almost all the problems:(
What's the need for reversing the list?
Listen carefully from 4:48
Because we're doing backtracking, since initial safe nodes are the terminal nodes and other safe nodes are those which points to the terminal node.
So in topo sort, U -> V means U comes before V, so if we reverse all the edges then from the terminal node we can find all the other safe nodes since they all points to the terminal node.
@@tusharbharane1484 Ok
Bhaiyaaa.... I have done a lot of questions in recursion. but when I started dp i felt like ki Mujhe to recursion hi nhi ata. how to deal with this thing. please tell me.
recursion series h na wo kr lo full, fir trees kro, fir dp kro, trees se visualisation bht badti hai recursion ki
@@takeUforward now i have done with your whole playlist of recursion and tress. Thank you so much for your content . can't express my gratitude in words.
Us
class Solution {
public:
vectordp;
vectorvis;
bool s(int node,vector& graph){
if(vis[node]) return dp[node];
bool p = 0;
vis[node] = 1;
for(auto i: graph[node]){
if(s(i,graph)) p = 1;
}
return dp[node] = p;
}
vector eventualSafeNodes(vector& graph) {
dp = vector(graph.size(),-1);
vis = vector(graph.size(),0);
for(int i=0;i
why did we reverse the nodes koi simple bhasha me samjayga pls i no understand
When u go for string Bootcamp
us
dude dont get burned out
why not 11 is the safe node have doubt?
It is safe node.....striver might have forgot that point
Did you understood the concept? It was after reversing it. Look at the graph before reversing :)
us :)
undrstood
this method definately not very intuitive when solving for first time, I did it by dfs first time
I don't know what edge case the interviewer will throw to use this instead of DFS.
I did the opposite of Kahn's algorithm topo sort. I found the outdegrees and then removed the incoming edges. But in leetcode, 105/112 test cases passed and after that i got TLE for a very large value.
Below is my code: Plz help me optimize this method.
class Solution {
public:
vector eventualSafeNodes(vector& graph) {
int n = graph.size();
vectoroutdegree(n,0);
queueq;
for(int i=0; i
it cannot be solved using adjacency list as list can point to neightbour but neighbour can not to parent ...and using matrix will take more time
I was able to use the same intuition of using outdegrees array + a reversed adjList
```
func eventualSafeNodes(graph [][]int) []int {
n := len(graph)
outdegrees := make([]int, n)
revAdjList := map[int][]int{}
q := []int{}
out := []int{}
for i := 0; i < n; i++ {
for _, nei := range graph[i] {
revAdjList[nei] = append(revAdjList[nei], i)
}
outdegrees[i] += len(graph[i])
if outdegrees[i] == 0 {
q = append(q, i)
out = append(out, i)
}
}
if len(q) == 0 {return nil}
for len(q) != 0 {
dq := q[0]
q = q[1:]
for _, nei := range revAdjList[dq] {
outdegrees[nei]--
if outdegrees[nei] == 0 {out = append(out, nei); q = append(q, nei)}
}
}
sort.Ints(out)
return out
}
```
@@OrbitZyro which language is this ?
@@amansinghal4663 golang
Understood!!!
understood
Understood
"understood"
Understood !!!
Understood!!!!
understood