G-21. Topological Sort Algorithm | DFS

In case you are thinking to buy courses, please check below:

---------------------------------------------------------------------------------------------------------------------------

[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

[srinayclg]

Many coder who know all this things but cannot explain well, but u r the different beast who can do both single handedly !!!!

[harshniteprasad]

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.

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

[AquaRegia-iu]

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.

[awesome_latest_virals]

we can use bool array instead of int array to mark visited....it will take less memory.

[ChiragDhamija-bn]

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

[hah]

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

[vineetatiwari]

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.

[SD-vkko]

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

[arushimathur]

Great Work Striver. Thanks for always helping us !!

[ishangujarathi]

loved the intuition and explanation striverr

[cinime]

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

[CodeMode]

explained in quite easy manner ..thanks habibi

[dsa_tutorial]

Thank you striver for providing such nice content

[shyren_more]

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

[NinjaPlayer]

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

[pulkitjain]

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);
}

[the_curious_engineer]

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

[hercules]

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