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
@arjunrai8126
Жыл бұрын
Understood
@pulkitjain5159
Жыл бұрын
@pulkitjain5159 0 seconds ago LET ME GIVE WHAT I UNDERSTOOD AS AN INTUTION Agar isko Task Completion ke perspective se dekhe such that if A -> B is like ki A wala task complete karne ke liye B wala task complete hona jaroori hai. toh hum dfs ke through bas yeh keh rahe hai ki dfs(task , completedTasks){ visited[task] = true; // mene yeh task karna start kardiya hai // par mujhe pata laga yeh task toh bakiyo pe dependent hai , toh phele mein unko khatam karke ata hu // let task on which my current task is dependend on be "dep". for( int dep : adj[ task ] ){ if(!visited[dep]){ // agae yeh dep abhi tak khatam nahi hua hai dfs(dep , completedTasks); // phele m isko complete kar leta hu } } // ab jab saare tasks jinpe mein depend karta hu khatam hogaye toh completedTask.push(task); }
@artofwrick
6 ай бұрын
Why can't we add codes in comments?
@srinayan390
Жыл бұрын
Many coder who know all this things but cannot explain well, but u r the different beast who can do both single handedly !!!!
@harshniteprasad5301
Жыл бұрын
Revising through this playlist before an interview is a bliss. INTUITION : incase you faced some trouble , taking in consideration the graph 1->2->3->4 we start with the dfs(1) we keep calling it for the adjacent nodes and at the very end we reach dfs(4) WHICH DOES NOT HAS ANY ADJ NODE, thus we put it in the stack stating that there is no node it needs to point after completion we push 3 in the stack stating that all the nodes pointed by 3 must already be the stack, same way we go up and at the end we push 1 in the stack stating that all the nodes pointed by 1 are already in the stack in a linear order. Linear order if a node v points to u then v comes first then u.
@sayandey2492
Жыл бұрын
And if it is reverse of topological ordering? Use Queue :P
@varunaggarwal7126
Жыл бұрын
@@sayandey2492 by playing with where you place stack during recursion you can use stack only.
@pulkitjain5159
Жыл бұрын
@pulkitjain5159 0 seconds ago LET ME GIVE WHAT I UNDERSTOOD AS AN INTUTION Agar isko Task Completion ke perspective se dekhe such that if A -> B is like ki A wala task complete karne ke liye B wala task complete hona jaroori hai. toh hum dfs ke through bas yeh keh rahe hai ki dfs(task , completedTasks){ visited[task] = true; // mene yeh task karna start kardiya hai // par mujhe pata laga yeh task toh bakiyo pe dependent hai , toh phele mein unko khatam karke ata hu // let task on which my current task is dependend on be "dep". for( int dep : adj[ task ] ){ if(!visited[dep]){ // agae yeh dep abhi tak khatam nahi hua hai dfs(dep , completedTasks); // phele m isko complete kar leta hu } } // ab jab saare tasks jinpe mein depend karta hu khatam hogaye toh completedTask.push(task); }
@sakshammisra189
Жыл бұрын
@@varunaggarwal7126 exactly what i was thinking , the moment you insert the ele should be made at the start and not end , regular dfs is rev topo i guess ?
@akash_assist
5 ай бұрын
great comments , it's okk for understanding, actually great but code is actually working in backtracking way, so not exactly fitting...... mtlb ki phle hum uss element ko khoj rhe hain jo sbpe dependent hain (dfs(1) agar dfs(2) ko call kr rha hain mtlb 1->2 ja skte hain mtlb ki 2 ko krne ke liye 1 ka hona jruri hain, lekin yha hum sbse phle 2 ko stack mein dalenge then 1 ko so that 2 sbse niche chala jaye,) isse jo kaam sbse phle krna hain, jo kisi pe dependent nhi hain wo top pe aajayega@@pulkitjain5159 this is from my understanding, please correct if i am wrong.🙏
@decepticonWave
Жыл бұрын
The problem with this solution is that if you are given a directed graph that contains a cycle in the solution. The algorithm wont be able to detect, it will spill out an ordering which is wrong. But when using khans algorithm, you will be able to detect whether top. sort was possible or not.
@guptashashwat
Жыл бұрын
+1
@tanyasingh2344
Жыл бұрын
Yeah but he already mentioned it is for Directed Acyclic Graph so it won't work in Graphs containing cycles.
@salmankhader1258
Жыл бұрын
But you can check the size of your topological sort array and if it is equal to number if vertices it is a valid one otherwise not.
@kartikdalai7998
Жыл бұрын
C ho tum
@uditgarg6508
10 ай бұрын
that is completely wrong@@salmankhader1258
@user-ie8sy7wo4m
Жыл бұрын
Quick Tip : If you are thinking, why don't we put into list when you start dfs, this way we don't have to use stack or reverse order. Consider a case 6->0->1->2->3->4->5, we start from 0 and put into list, so ordering comes out to be, 0,1,2,3,4,5 and then we check for 6, so 6 at last, but this is wrong. Hence we cannot put into list when starting the dfs, because we dont' know if 0 was coming from somewhere else. Hence we put into list at last and then reverse(or use stack and pop). So ordering becomes 5->4->3->2->1->0 and then we check for 6, so 5->4->3->2->1->0->6 and reversing this is correct topo.
@vinayjangra1401
11 ай бұрын
Thanks bro !!
@crosswalker45
10 ай бұрын
Why 6 cannot be in last?
@user-ie8sy7wo4m
10 ай бұрын
@@crosswalker45 Because 6 is at starting of topo sort and not last. It is even before 0, since we started from 0 doesn't mean our topo start from 0.
@priyanshkumar_iitd
3 ай бұрын
Thanks
@pulkitjain5159
Жыл бұрын
LET ME GIVE WHAT I UNDERSTOOD AS AN INTUTION Agar isko Task Completion ke perspective se dekhe such that if A -> B is like ki A wala task complete karne ke liye B wala task complete hona jaroori hai. toh hum dfs ke through bas yeh keh rahe hai ki dfs(task , completedTasks){ visited[task] = true; // mene yeh task karna start kardiya hai // par mujhe pata laga yeh task toh bakiyo pe dependent hai , toh phele mein unko khatam karke ata hu // let task on which my current task is dependend on be "dep". for( int dep : adj[ task ] ){ if(!visited[dep]){ // agae yeh dep abhi tak khatam nahi hua hai dfs(dep , completedTasks); // phele m isko complete kar leta hu } } // ab jab saare tasks jinpe mein depend karta hu khatam hogaye toh completedTask.push(task); }
@noob_coder8926
2 ай бұрын
nice explanation
@jotsinghbindra8317
2 ай бұрын
ek dum sexy explanation bhai!
@kunalarora3885
2 ай бұрын
Very clearly explained @pulkitjain5159, @striver this is what you call intuition
@imafraidjumitebeeinnagang3886
Ай бұрын
Should have just read this instead of watching the video, so good!
@parthivsinhvaghela6100
4 күн бұрын
it is like deadlock
@awesome_latest_virals6098
Жыл бұрын
we can use bool array instead of int array to mark visited....it will take less memory.
@SD-vk3ko
Жыл бұрын
Hey Striver, Thank you for the amazing content. But I request if you could add some problems on Union Find as well. Thanks in advance!!!
@the_curious_engineer
Ай бұрын
whenever your heart is broken , don't ever forget you are golden..
@hah314
Жыл бұрын
Can't express it in words, your content is out of the world, really amazing bro❤❤
@arushimathur7205
Жыл бұрын
Great Work Striver. Thanks for always helping us !!
@user-mm7mc6io5v
Ай бұрын
Hey striver Instead of using a stack we can directly store it in a vector and write ans.push_back(node) and just when returning the final anwerr we can reverse this vector This will help us to optimize the space complexity
@ishangujarathi10
Жыл бұрын
loved the intuition and explanation striverr bhaii
@stith_pragya
8 ай бұрын
Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@cinime
Жыл бұрын
Understood! Super amazing explanation as always, thank you very much!!
@sripriyapotnuru5839
Жыл бұрын
Thank you, STRIVER 🙂
@shyren_more
Жыл бұрын
understood, was able to code up using the logic after your explanation, thanks!
@user-tk2vg5jt3l
3 ай бұрын
Thank you bhaiya
@abhijeetkumar2970
11 ай бұрын
The intuition behind the problem: The hint here lies in the definition of topological sort as we need the least dependent element first we add it at last(thus using stack). When a node finishes all it's calls, all the elements that should come after it would already be inserted to the stack and now we only need to add current node to the stack. Thus we can be confident about adding node to stack as all it's children are already processed.
@artofwrick
6 ай бұрын
A > B >C and A>D>C. How does that work with a stack?
@abhijeet19403
6 ай бұрын
@@artofwrick At first make the adjacency list A- B,D B- C D- C Also make a visited array Start traversing from A to D At first A is not visited so mark it visited and call it's neighbors As B has also one neighbor we call it C has no neighbors (or child nodes) so the dfs stops and we add C to the stack Then B is added as now it has no more children Then D is called from A D tries calling it's children (C here) but it is already visited so we simply add D to stack At the end A is also added to the stack Thus the final contents of the stack are A D B C which is a valid topo sort
@dsa_tutorial
Жыл бұрын
Thank you striver for providing such nice content
@CodeMode9313
Жыл бұрын
explained in quite easy manner ..thanks habibi
@GeetainSaar
Ай бұрын
Happy guru purnima ❤🎉
@suryanshsingh6423
Ай бұрын
Understood. Fantastic explanation❤
@AppaniMadhavi
2 ай бұрын
Even without taking a stack we can do, it is by taking a vector and storing all the node values after completion of that node's dfs, and finally reverse that vector...
@harshith4549
2 ай бұрын
Why to go all the way to reverse a vector rather than storing it in the reverse order during the dfs. Just create a vector with size of total number of nodes and using a index variable move from the back of vector to the front during dfs. Here's how its done: class Solution { private: void dfs(int start,int vis[],vector adj[],vector& ans,int& index){ vis[start]=1; for(auto it: adj[start]){ if(!vis[it]){ dfs(it,vis,adj,ans,index); } } ans[index--]=start; // Its decrement } public: //Function to return list containing vertices in Topological order. vector topoSort(int V, vector adj[]) { // code here int vis[V]={0}; vector ans(V); int index=V-1; for(int i=0;i
@shubhranginidas6818
3 ай бұрын
We should apply the DFS way of Topological Sorting only if the ordering of the resulting sort is checked otherwise should always prefer BFS way of Topological Sorting. WHY? Because if the cycle exists DFS would return all the vertices with wrong ordering but in case of BFS, it wouldn't return all the vertices if cycle exists. So even if we don't go for ordering detection, number of vertices itself would clear whether sorting is possible or not. This is the reason why BFS (Kahn's Algorithm) is preferred.
@lonersunited
6 ай бұрын
Understood 😊
@LearnWithMe7777
Ай бұрын
Understood❤
@rutikjalhare6836
Жыл бұрын
GOD level explanation
@vaalarivan_p
Жыл бұрын
4:05 - 7:50
@user-hn3pf5pb3n
23 күн бұрын
Very Well Understood!!
@shubhipaul6830
Ай бұрын
For a long time I believed topo sort to be hard. Guess one just has to find the right explanation.
@Maunil2k
3 ай бұрын
I believe we need to assume that the given directed graph does not contain any cycle, only then this algorithm using DFS will work.
@Saurabh-fe2bg
Жыл бұрын
got it!! thanks for this series
@hercules3150
Жыл бұрын
Thank you sir iski bahut need thi. Haal hi mai ek question aaya tha aur woh mai nhi kar paya tha
@tsk1217
9 ай бұрын
FOR REVIEWING THE CODE FOLLOW THIS - class Solution { private: void DFS(int start, vector&visited, vector adj[] , stack&stack){ visited[start]=1; for(auto x:adj[start]){ if(!visited[x]){ DFS(x,visited,adj,stack); } } stack.push(start); } public: //Function to return list containing vertices in Topological order. vector topoSort(int V, vector adj[]) { // declaring a visited array and initially filled with 0 vectorvisited(V,0); stackstack; for(int i=0;i
@rishabhgupta9846
Жыл бұрын
understood,great explanation
@prajaktachachad477
4 ай бұрын
Amazingly explained :)
@kamikaze9245
Жыл бұрын
Understood bhaiya
@banothutharun2743
Ай бұрын
understood striver bro
@utkarshsharma1185
Жыл бұрын
understood bhaiya..
@himaniupadhyay8201
Жыл бұрын
Thank You sooo much SIR 🙏
@renuroy4826
3 күн бұрын
Understood.
@ajith4249
11 ай бұрын
In Reverse Order # another approach class Solution: #Function to return list containing vertices in Topological order. def topoSort(self, V, adj): # Code here stack=[] def dfs(node,adj,stack,vis): vis[node]=1 for item in adj[node]: if vis[item]==0: dfs(item,adj,stack,vis) stack.insert(0,node) vis=[0 for i in range(V)] for i in reversed(range(V)): if(vis[i]==0): dfs(i,adj,stack,vis) return stack
@lanslord11
4 ай бұрын
Intuition part is what made this whole video amazing for meeee
@user-bc6ss6gp3z
4 ай бұрын
#Striver rocks 🤟👍
@tasneemayham974
5 ай бұрын
THANK YOUUU STRIVERRR!!
@pranayjain._
Жыл бұрын
Understood! Thank you sir
@bro_code3505
Жыл бұрын
hey striver I want to code like you!!
@UECAshutoshKumar
11 ай бұрын
Thank you sir 😊
@DevashishJose
6 ай бұрын
Understood, Thank you so much
@amitp277
Жыл бұрын
Awesome work
@vakhariyajay2224
Жыл бұрын
Thank you very much. You are a genius.
@sakshammisra189
Жыл бұрын
intuition is that we want reverse of the DFS as when dfs is completed then we are inserting which tells us A->B , then we are inserting B and then A , but we reverse it to get A and then B .
@yuvrajanand9342
Жыл бұрын
only had to watch half of the video and did the coding part all by myself
@worthlessguy1621
4 ай бұрын
understood the assignment :)
@atharvadeshmukh6328
5 ай бұрын
Understood!
@evilpollination1916
3 ай бұрын
Understood Striver bhai. Aapne samjhaya hai toh samjh to aayega. Also bhai aapki tabayt kharab lag rahi thi . Pls take care bhai.
@mananarora141
Жыл бұрын
UNDERSTOOD!!!!!!!
@saranavinash9261
8 ай бұрын
You should have included or referred to the graph representation, so that we can get idea about how the adjacent nodes are stored and traversed.
@amanasrani6405
4 ай бұрын
understand bhaiya❤🙏🏻\
@kunal4710
Жыл бұрын
UNDERSTOOOOOD😊
@Swiftie13498
6 ай бұрын
Understood!!
@The_Shubham_Soni
11 ай бұрын
UNDERSTOOD.
@user-kl3qv1sc8k
2 ай бұрын
Understood Striver
@CHOWDAVARAPUSAIDEEPAK
4 күн бұрын
Given , the algorithm achieves the desired output of topologically sorted array , but there can be many no of possible array sequences that are valid for the same graph . So , How do i get an array that's topologically and lexicographically sorted too?
@SurajGupta-gc9tz
Ай бұрын
Understood
@nikitakeshri9233
Ай бұрын
Understood:)
@user-fx3bn4co5o
Жыл бұрын
Its awesome bro
@harshdasila6680
Жыл бұрын
understoooddddd
@rayyansyed2998
10 ай бұрын
"understood"
@deepanshusharma142
25 күн бұрын
understood
@ashishbhardwaj4334
Жыл бұрын
Understood..
@akashsahu2571
Жыл бұрын
yes
@saikrishna872
Жыл бұрын
UNDERSTOOD
@ayushgaurabh8604
2 ай бұрын
awesome
@kirtitung4877
Жыл бұрын
understood!!! JOD
@cypher7536
Жыл бұрын
understood ❤️
@arkasheikh3539
Жыл бұрын
"UNDERSTOOD"
@subhadeepghosh2813
Жыл бұрын
maza aa gya
@soicooc3500
4 ай бұрын
5:30
@soicooc3500
4 ай бұрын
4:08
@prajwalhorti3717
Жыл бұрын
understood!
@akshatpandey2609
Жыл бұрын
can we pushback the node in ans in the postorder of the dfs function i.e., after the for-loop?
@rohit2571
Жыл бұрын
then you have to reverse the stack.
@sanadkhan1
Жыл бұрын
kzitem.info/news/bejne/l4yfm4iamJNpdW0&ab_channel=Pepcoding watch this for your doubt clarification
@yashsaxena7787
9 ай бұрын
g.addEdge(1,2); g.addEdge(1,3); g.addEdge(2,4); g.addEdge(2,5); g.addEdge(3,6); g.addEdge(3,7); why not working for this graph?????
@yashsaxena7787
9 ай бұрын
#include #include #include using namespace std; class Graph{ private: int V; vectoradj; void topologicalSortUtil(int v, vector&visited , stack&stack){ visited [v]=true; for(int i:adj[v]){ if(!visited[i]){ topologicalSortUtil(i,visited,stack); } } stack.push(v); } public: // constructor to initialize the graph with the number of vertices Graph(int vertices){ V=vertices; adj.resize(V); } void addEdge(int u,int v){ adj[u].push_back(v); } vector topologicalSort(){ vector visited (V,false); stackstack; for(int i=0;i
@priyanshkumar_iitd
3 ай бұрын
It's working...
@codingalley6229
Жыл бұрын
🐐
@rahulhembram4519
Жыл бұрын
UnderStood
@felipesantiagogama2833
Жыл бұрын
understood.
@1tav0
Жыл бұрын
Awesome! Us
@shivendrasingh8520
2 ай бұрын
can we use queue in this question at last we will reverse the queue
@anssha2643
Жыл бұрын
Why aren't we using the path[] here? Is it because its acyclic graph?
@AdityaKumar-uf5xp
Жыл бұрын
understood but striver I forgot those code and have to remember everytime . How should I keep remember the code?
@diksha3157
Жыл бұрын
Don't memorise the code. Instead, try to understand the logic and then write code. Converting logic into code requires practice.
@Moch117
11 ай бұрын
Memorize the logic. If DFS, and topological sort, use a stack. BFS, use Queue. Both use visited array
@oqant0424
Жыл бұрын
understood!!!!!!!!!!!!!!!!!!!!
@valarmorghulis9244
Жыл бұрын
What I understood from this problem is that "GIve a BFS path using DFS". Is it?
@sagargujarathi754
Жыл бұрын
Awesome
@avi7629
Жыл бұрын
Cool understood
@gurudekirtaniye9001
Жыл бұрын
Understood but what the intuition ?
@UmeshYadav-qx4hr
8 ай бұрын
link is not found for -C++/Java/Codes and Notes Link Please check.
@Incurabl
Жыл бұрын
6:20
@bro_code3505
Жыл бұрын
how do we know that stack will be used
@narendrarokkam5367
Жыл бұрын
Because we need to get in reverse order
@soumyamondal
Жыл бұрын
@@narendrarokkam5367 we can store it in a vector then simply reverse it, space saved right?
Пікірлер: 243