G-21. Topological Sort Algorithm | DFS

[@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

[@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]

Why can't we add codes in comments?

[@Saritha_Dhandapani]

Understood, thanks a lot.

[@srinayclg390]

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]

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]

that is completely wrong@@salmankhader1258

[@AquaRegia-i3u]

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]

Thanks bro !!

[@crosswalker45]

Why 6 cannot be in last?

[@AquaRegia-i3u]

@@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.

[@imPriyansh77]

Thanks

[@ChiragDhamija-b4n]

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

[@tummalapallikarthikeya2412]

yeah! same opinion

[@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!!!

[@hah314]

Can't express it in words, your content is out of the world, really amazing bro❤❤

[@vineetatiwari5060]

One corner case - Say if we get nodes in queue that have 0 indegree plus 0 adjacent node as well, this will give us incomplete answer. 10 9 dhhid dahi cedg fg gdah i gbdei hbgf e ddde Here, in queue -> 0,1,9 will be added and none of them will have adjacent nodes as well so our answer will become incomplete. So always check the length of your topo answer whether its equal to k or not. If it is equal then return the string otherwise empty string. PS - We can use visited array also here.

[@gopichandreddy7598]

give on more clear example on the corner case, and also don't forget to provide the expected and actual output.

[@arushimathur7205]

Great Work Striver. Thanks for always helping us !!

[@ishangujarathi10]

loved the intuition and explanation striverr bhaii

[@NinjaPlayer005]

Making graph feel as easy as binary search something only very few like striver can do!

[@cinime]

Understood! Super amazing explanation as always, thank you very much!!

[@the_curious_engineer]

whenever your heart is broken , don't ever forget you are golden..

[@yashcoder291]

golden nhi , goal then

[@the_curious_engineer]

@@yashcoder291 thanxx for correcting.

[@stith_pragya]

Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@shyren_more]

understood, was able to code up using the logic after your explanation, thanks!

[@sanchitkaul5084]

Nice Explanation! Looks like your energy was low in this video , but I guess thats the right amount of energy to have . over energetic is a waste of breath and time. Just a well wisher with constructive criticism . Good Work Striver !

[@CodeMode9313]

explained in quite easy manner ..thanks habibi

[@dsa_tutorial]

Thank you striver for providing such nice content

[@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]

nice explanation

[@jotsinghbindra8317]

ek dum sexy explanation bhai!

[@kunalarora3885]

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]

it is like deadlock

[@suryanshsingh6423]

Understood. Fantastic explanation❤

[@hercules3150]

Thank you sir iski bahut need thi. Haal hi mai ek question aaya tha aur woh mai nhi kar paya tha

[@sripriyapotnuru5839]

Thank you, STRIVER 🙂

[@AppaniMadhavi]

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]

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

[@abhijeetkumar2970]

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]

A > B >C and A>D>C. How does that work with a stack?

[@abhijeet19403]

​@@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

[@lanslord11]

Intuition part is what made this whole video amazing for meeee

[@Saurabh-fe2bg]

got it!! thanks for this series

[@GeetainSaar]

Happy guru purnima ❤🎉

[@rutikjalhare6836]

GOD level explanation

[@prajaktachachad477]

Amazingly explained :)

[@rishabhgupta9846]

understood,great explanation

[@lonersunited]

Understood 😊

[@pranayjain._]

Understood! Thank you sir

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@vaalarivan_p]

4:05 - 7:50

[@shubhranginidas6818]

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.

[@antor.morsalin]

Amazing Explanation

[@himaniupadhyay8201]

Thank You sooo much SIR 🙏

[@kaichang8186]

understood, thanks for the great video

[@yashsaxena7787]

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]

#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

[@imPriyansh77]

It's working...

[@ajith4249]

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

[@Maunil2k]

I believe we need to assume that the given directed graph does not contain any cycle, only then this algorithm using DFS will work.

[@DevashishJose]

Understood, Thank you so much

[@shubhipaul6830]

For a long time I believed topo sort to be hard. Guess one just has to find the right explanation.

[@utkarshsharma1185]

understood bhaiya..

[@tasneemayham974]

THANK YOUUU STRIVERRR!!

[@CHOWDAVARAPUSAIDEEPAK]

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?

[@yuvrajanand9342]

only had to watch half of the video and did the coding part all by myself

[@kamikaze9245]

Understood bhaiya

[@swaraj.nalawade.4634]

class Solution { private: void dfs(int start, vector adj[], int vis[], stack &st){ vis[start] = 1; for(auto &it : adj[start]){ if(!vis[it]){ dfs(it, adj, vis, st); } } st.push(start); } public: //Function to return list containing vertices in Topological order. vector topoSort(int V, vector adj[]) { int vis[V] = {0}; stack st; vector ans; for(int i=0; i

[@DeepanshiBhardwaj-y1t]

Very Well Understood!!

[@worthlessguy1621]

understood the assignment :)

[@UECAshutoshKumar]

Thank you sir 😊

[@AyushGupta-ux4gq]

at 5:39 ohh thats all lets code void dfs(int node,vector adj[],vector &visited,stack &st) { if(visited[node]==1) { return; } else { visited[node]=1; for(int i=0;i

[@amitp277]

Awesome work

[@evilpollination1916]

Understood Striver bhai. Aapne samjhaya hai toh samjh to aayega. Also bhai aapki tabayt kharab lag rahi thi . Pls take care bhai.

[@Rieshu-l9i]

#Striver rocks 🤟👍

[@kunal4710]

UNDERSTOOOOOD😊

[@Learnprogramming-q7f]

Thank you bhaiya

[@amanasrani6405]

understand bhaiya❤🙏🏻\

[@tushar_kesharii]

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

[@Tbm4545]

Hlw means this is similar to dfs only difference is here we use a xtra stack to get topo sequence

[@manishprajapat9135]

@take U forward before applying this method we should ensure that no cycle is present ??

[@VIRAJBHOSLE]

Input is always DAG, so it's not checked. But if input can be cyclic graph, you need to add cycle checks

[@imPriyansh77]

@@VIRAJBHOSLE Yeah, thanks!!!

[@bro_code3505]

hey striver I want to code like you!!

[@yashshukla1637]

So So So good!

[@anssha2643]

Why aren't we using the path[] here? Is it because its acyclic graph?

[@user-fx3bn4co5o]

Its awesome bro

[@kirtitung4877]

understood!!! JOD

[@valarmorghulis9244]

What I understood from this problem is that "GIve a BFS path using DFS". Is it?

[@vinaynalluri277]

everything is nyc except one thing sir if suppose i/p is loop(1,2,3) then s.size==n fails only bfs accepts am i correct i chckd for conditions

[@banothutharun2743]

understood striver bro

[@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]

kzbin.info/www/bejne/bIfMZoealMZreJo&ab_channel=Pepcoding watch this for your doubt clarification

[@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 .

[@mananarora141]

UNDERSTOOD!!!!!!!

[@saranavinash9261]

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.

[@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]

Memorize the logic. If DFS, and topological sort, use a stack. BFS, use Queue. Both use visited array

[@shivendrasingh8520]

can we use queue in this question at last we will reverse the queue

[@bestsaurabh]

vis array was not passed as reference, still it worked???

[@suryakiran2970]

Understood❤

[@UmeshYadav-qx4hr]

link is not found for -C++/Java/Codes and Notes Link Please check.

[@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?

[@babai2196]

@@soumyamondal but time inc

[@The_Shubham_Soni]

UNDERSTOOD.

[@gurudekirtaniye9001]

Understood but what the intuition ?

[@cypher7536]

understood ❤️

[@MindsetMotivation75]

is it ok to use queue rather than using a stack ?

[@Shivanai_h]

Yes but at last when you pop out nodes, you will have to reverse the resultant list.

[@MindsetMotivation75]

@@Shivanai_h thank you 😊

[@soumyamondal]

@Ayush Negi simply use vector, and reverse it. No need to store again to vector from deque while returning.

[@harshmishra5331]

Why can we not use simple array instead of stack. I am not able to understand of specific stack in this case. Can any body clear this?

[@TheBillionairesWorld]

Yes we can push into vector..... Than at the end we can reverse it

[@sumerrawat6947]

Understood !

[@saurabhpandey4427]

class Solution { public: void dfs(int node, vector &Vis, stack &st, vector &adj) { Vis[node] = true; for (auto neighbor : adj[node]) { if (!Vis[neighbor]) { dfs(neighbor, Vis, st, adj); } } st.push(node); } bool isPossible(int N, int P, vector &prerequisites) { vector adj(N); for (auto pre : prerequisites) { adj[pre.second].push_back(pre.first); } stack st; vector Vis(N, false); for (int i = 0; i < N; i++) { if (!Vis[i]) { dfs(i, Vis, st, adj); } } stack reversedSt; // Stack to reverse the order while (!st.empty()) { reversedSt.push(st.top()); st.pop(); } return N == reversedSt.size(); } };....why this code is not working for prerequisites problem ?

[@subhadeepghosh2813]

maza aa gya

[@harshdasila6680]

understoooddddd

[@abhinavkohli4293]

what if i run this algo on a directed graph with cycle

[@imPriyansh77]

Topological Sorting - DFS algorithm will print wrong linear ordering if input is a directed cyclic graph.

[@soicooc3500]

5:30

[@GeneralistDev]

Stack is not necessary. We could have used a vector also

[@imPriyansh77]

but need to reverse the array

[@soicooc3500]

4:08

[@heybuddy_JAI_SHREE_RAM]

grt vdo

[@saikrishna872]

UNDERSTOOD

[@per.seus._]

understoood

[@arkasheikh3539]

"UNDERSTOOD"

[@DeadPoolx1712]

UNDERSTOOD;