Kosaraju Algorithm | Strongly connected components in a graph

This video explains the Kosaraju algorithm which is used to find all the strongly connected components in a graph.We can even use this algorithm to find if the given graph is strongly connected or not.I have shown the concepts of strongly connected components in the beginning of the video and then explained some properties of graph which we can use to find the strongly connected components.I have explained the kosaraju algorithm using simple DFS and stack.This is a 3 step process.The first step is to traverse the graph using DFS and then push the nodes in stack.The second step is to find transpose of the graph, that is, reverse all the edges in the graph.The third step is to pop nodes one by one from stack and make DFS calls to find the nodes in a strongly connected component.I have also shown why the kosaraju algorithm logic works using the transpose graph logic.At the end of the video, I have explained the code walk through.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to appreciate our effort /\ and to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOS:-
Prims Algorithm: • Prims algorithm | MST ...
Kruskals Algorithm: • Kruskals algorithm | C...

[@adityaojha2701]

The unique thing about your explanations is you not only explain algorithm but also explain how to implement that using dry runs which are great.

[@techdose4u]

Thanks

[@adityaojha2701]

@Callen Emory do not fall into this whosoever reading this comment. It's a spam.

[@adityaojha2701]

@Mark Josiah 😂😂 trap

[@himanshu2149]

Fluent English + Beautiful Presentation + Superb Examples + Best Explanation = TECH DOSE

[@techdose4u]

😊

[@vaibhavsingh-fu1vg]

Loved the premise !! That's what made your explanation different from other videos that I came across!

[@techdose4u]

Thanks

[@battlecrusecruse9155]

the best explanation over the internet
this guy must be protected at any cost.

[@techdose4u]

Thanks 😊

[@iamakifislam]

You are the boss. You have absolutely clear my concept of SCC. Your channel deserves 1 Million ❤️ Thank you for the video.

[@techdose4u]

Welcome :)

[@abhilashsulibela1414]

This is amazing! a very clear flow of thought. Thank you for making this & I request you to please continue to make such high-quality videos

[@techdose4u]

Welcome :)

[@svworld01]

Here I found the best explanation of this algorithm. Thank You :)

[@techdose4u]

Welcome :)

[@mayukhbhowmik934]

Superb Content, Just spellbound after watching the tutorial.

[@mayankchauhan6680]

You are an amazing teacher. I mean everything taught by you seems very simple even if it's not.

[@techdose4u]

Thanks

[@ClashWithSwap]

Loved the explanation. Could you make one on bridges and articulation points too? You make graphs easy!

[@techdose4u]

Thanks. Those are the upcoming topics 😁

[@shubhamagarwal2998]

@@techdose4u thanks bhaiya

[@Learner010]

@@techdose4u thanks

[@shuvadiproy5154]

Best and easiest explanation....And feeling proud of that Kosaraju Algorithm was discovered by an Indian .

[@sahilnegi2789]

Sir your content is so amazing that after watching your lecture I thought it is so simple. thanks again .
keep uploading this amazing content . you

[@Cruz0e]

Beautiful explanation, I usually have hard times to understand tutorials in Indian accent. So when I googled I had to turn pages to find one that isn't Indian. First I watched that other video (with not Indian accent) on the subject. But it was horrible. Then said I give a try, and I chose this video.
I have to say your explanation is beautiful, clear and easy to understand, the accent is barely noticeable. I like it! Great job!
(Obviously. Liked and Subscribed.)

[@techdose4u]

Thanks :)

[@charikgoyal5612]

bhai aap gajab ho like truly god of algorithms 🙌🙌

[@techdose4u]

😅

[@ytuser659]

Was waiting for this. Thank you!

[@techdose4u]

Welcome :)

[@manavkumarjaiswal2734]

Just got the perfect reason which I was eagerly searching for
Great explaination
adios

[@techdose4u]

Great

[@letsdoeverythinginoneweek9398]

Thnk u sir mazaa aa gayi
itna acha explanation Nahi Suna mena .
Keep more videos .

[@bablushaw6856]

It feels good when I see your video in TH-cam result list of my problem. Nothing else to try then.

[@goblin1390]

Graph algorithm ans especially implementation was a nightmare.Thanks for very easy explanation. Please make more videos related competitive programming topics.

[@vijaykumarlokhande1607]

why I love the explanation? simple bcoz clear voice, dark background, and content flow.

[@techdose4u]

:)

[@indiansoftwareengineer4899]

Thanks a lot Surya bro, your videos are gems, awesome work.

[@ankitsoni3388]

Awesome bro, would like to meet you sometime. It's really hard to take out time from your daily schedule and create such amazing content. Thanks alot!!

[@techdose4u]

Welcome. Sure 🙂

[@deathicon3405]

In both the examples you showed, you started from a node which in the SCC with outgoing edge,
What will happen if it was an ingoing edge, like what will you in your first DFS?

[@PRANAVMAPPOLI]

You can do a DFS that we use for unconnected components and use a common stack for all dfs call. That will works

[@SurajKumar-bw9oi]

If I would be a teacher I would like to teach like you. Great explanation.

[@abhinaygupta]

Great explanation. Converted Kosaraju in simple dfs.

[@ashreetpatnaik9735]

Beautiful explaination ❤️🔥🔥🔥 please don't stop we will support you 😊

[@techdose4u]

Thanks :)

[@vojtechrozhon362]

Absolutely amazing work!

[@techdose4u]

Thanks :)

[@sharuk3545]

One of the best Solution on entire platform.... Thnk u SOoooooo much broooooo make more videos

[@techdose4u]

Welcome :) Sure

[@mohnishsinghbhamra]

Love to see graph algorithms in your channel

[@techdose4u]

😁 Nice

[@togiraikonoka9664]

love it! lowkey saved my life ngl

[@EngWorld-nr2ww]

best explanation of kosaraju till now..

[@techdose4u]

Thanks :)

[@puneethj9920]

This is amazing and the best explanation.

[@sandutozlovanu9353]

Best video ever !

[@abhijitmishra7736]

Great Video

[@georgemullarjampana]

underrated video

[@techdose4u]

😅

[@piyushlohiya1977]

Explanation is so good👍

[@abheetsingh9938]

if were a teacher in our college , the attendance in the classroom would be 100% .....Thanks a lot for your hard work :)

[@techdose4u]

Welcome 😃

[@danym-98]

Great explanation!

[@SUJOYPAULJOBS]

khub valo video ta....i puro buje giyechi vi...thank you bro.

[@techdose4u]

Emni korte thako👌🏼

[@SUJOYPAULJOBS]

@@techdose4u OK BRO

[@karanveersingh5535]

U made it so simple 🔥

[@syeedtalha1550]

Thank you so much

[@RahulKumar-si5dp]

Enjoyed a lot and...also learned ...
You made this understand so easy ...

[@techdose4u]

Thanks 😀

[@UtkarshSingh-qn9xu]

Instead of pushing the elements in the stack during backtracking, we can directly push the element as we are moving ahead, in that case, we won't even require to reverse the graph. Secondly, a point was missing here. While doing a DFS, if we are unable to reach every node, we must again do the DFS on the remaining ones. The example taken satisfied the approach but it can have many more cases. Still, I could think all this because I could understand what you explained in this video. Thanks. Do consider these points and let me know if I am going wrong.

[@spatil689]

Even I am having the same doubt can we do this?

[@tlado5370]

Thank you, this was very helpful!

[@techdose4u]

Welcome :)

[@hsetareh]

Excellent explanation.

[@SuperLucasGuns]

this was sensational

[@nirmalbabu9570]

thanks a bunch. The visual dry run was very helpful

[@techdose4u]

👍

[@ssshukla26]

Really good explanation. Thank you.

[@yangsiyu007]

Super video! I applauded for $2.00 👏

[@techdose4u]

Thanks for your support ❤️

[@raysk4798]

Thanks for the clear explanation!

[@techdose4u]

Welcome

[@agynbolatov7018]

thank you!

[@Naaz-2002]

Thank u so much, you made it so easy to understand!

[@techdose4u]

Thanks :)

[@ashutoshkumar4267]

Thank you for making Graphs so easy

[@techdose4u]

Welcome :)

[@than0s869]

nice explanation sir... :)

[@kongzilla2897]

Loved it :)

[@techdose4u]

Nice :)

[@srinivaskarthik1692]

Everything is perfect !!
Except to the fact that you could have shed some idea on why there was a usage of Stack here ( I could have traversed from any node , why any particular order from stack ?? )... . which would make us applaud for the genius Kosaraju.

[@techdose4u]

That is because if you jump from one SCC to another and then if you reverse edges, you can't jump from the same SCC to other one where you could have been able to jump prior to reversing.

[@srinivaskarthik1692]

@@techdose4u Thank you, i know the reason but few others in the comments had doubt on the usage of stack , hence I mentioned it would be great if it was explained in the video.

[@Learner010]

very well explained!

[@techdose4u]

Thanks :)

[@suryakiran2970]

Excellent

[@akshaycharjan6384]

Thanks a Ton :)

[@techdose4u]

Welcome :)

[@amgadshrief7215]

you are awesome keep going bro

[@techdose4u]

thanks :)

[@HarshKumar-nh6be]

Very very great explanation sir❤❤

[@techdose4u]

Thanks ❤️

[@suharajsalim4549]

Wow Thanks a lot :)

[@techdose4u]

Welcome :)

[@fahadisrar2195]

that was Helpful..Thanks!!

[@techdose4u]

Welcome :)

[@mdimranhosen6674]

You deserve this: 💚:

[@techdose4u]

Thanks 😊

[@mahipalsingh-yo4jt]

how are we able to know the particular node from which the first dfs is starting.? Because if we start dfs from any node another than 0 than we will have to make manual jumps and we will not be able to push all the elements to the stack without manually verifying that all the nodes have been visited...

[@umarteachestechwith2others803]

Thank you for amazing explanation but a little correction here. In case of undirected graph we call component a "connected component" not strongly connected component. SCC term is specifically used for directed graph if there is directed path from v to u and u to v.

[@anuragagarwal9617]

The explanation is great and very helpful to me, thanks @TECH DOSE

[@techdose4u]

Welcome 😀

[@vikashdhania2970]

👍👍👍👍

[@vedantshinde2277]

Best explanation I've come across! Would the algorithm work if we started with a random node in the graph for step1 instead of '0'?

[@musicnition1063]

Hi, at Minute 16:18 I check the vertex of the transposed graph. I don't go to three, because 3 is already traversed. Then I go to node 6 and write 6 to the SCC of 4. WHY? Don't I have to WAIT until I "see" that both 4 and 6 are in the SAME SCC? How do you see that?

[@kunalsoni7681]

Amazing session 💞🥰 I learn alot from this algorithm. Thanking you so much sir

[@techdose4u]

Welcome :)

[@kishantiwari3221]

Thank You Sir!

[@techdose4u]

Welcome

[@ritikmathur7469]

Nice!

[@techdose4u]

Thanks :)

[@anshuofficial166]

why we used stack, we can use for loop at second time DFS?

[@ratneshpal6026]

@ TECH DOSE, very informative video.
There is a small suggestion....
While showing the code...please zoom your code editor so that it is properly visible.
Thanks.

[@techdose4u]

I will try to make the font larger from next time.

[@pythonwithsi]

thank you bro.

[@piyushlohiya1977]

Can anyone tell me do we really need stack we can just take transpose and do dfs traversal the one which are not visited :++cnt

[@ivanvachilia4183]

Thanks!

[@techdose4u]

Welcome

[@samirpaul2]

🙌🔥🔥🔥🔥👍✨✨👌

[@maheshvoleti6990]

what if we start our first dfs with node in second ssc?

[@aanuraag83]

Thank you : )

[@techdose4u]

Welcome

[@ashishgor2163]

Thank you sir

[@footballfanatics007]

Great explanation

[@techdose4u]

Thanks 😊

[@mysteriesandfacts4u22]

Best explanation

[@techdose4u]

Thanks 😊

[@manjus3]

Hi @tech dose, thanks for this excellent video on Kosaraju's algorithm. Just had a question: After you have identified all the strongly connected components, how do you find the in_degree and out_degree of an entire SCC? Thanks!

[@abhishekshankar1136]

you can maintain an array of vector for each strongly connected component, for each vertice u , for each v in adjacent of u you can do indegree of v ++ and outdegree of u ++ , time complexity will be O ( V+E )

[@theghostwhowalk]

Amazing. Thanks for this video. If one has to detect if there is cycle in Directed graph, is Kosaraju algo way to go? We can’t do normal DFS.

[@techdose4u]

You can use same logic of finding strongly connected components. DFS with visited should work. We could have also used coloring.

[@naman_goyal]

very nice explanation

[@techdose4u]

Thanks :)

[@sujan_kumar_mitra]

Hey, what if instead of reversing the edges, we reverse the stack and perform dfs.. Will it generate wrong output?

[@techdose4u]

No it won't work. On reversing edges, the connecting edge between SCC is reversed. If you take SCC as just a single node then the graph will be a DAG. Our goal here is to detect when we move from one SCC to another. For that reason, you will require that edges are reversed so that you can't traverse more than 1 SCC using DFS only once. You need to manually make the jump.

[@mustafa-ahmed-dev]

thank you

[@soumambanerjee1816]

Awesome

[@techdose4u]

Thanks

[@beingSenpai]

can any one tell me
its a dumb question but please help Me
what if they given the graph in the inverse way then as per kosaraju if we reverse again we go from 0 to 7

[@shantamshrestha2070]

Sir your videos are wonderful. Please create videos on Word Break I and II problems on leetcode. Shall be grateful

[@techdose4u]

Sure :)

[@rahulchudasama9363]

Awesome explaination,
What is the application of this algo?

[@mustafa-ahmed-dev]

what is the blackboard you are using

[@ritikgoyal6087]

Can we interpret this question as we have to found all the cycles and the respective value of nodes present in them and at last we will consider all those nodes as seperate connected components which are not involved in any cycle.

[@techdose4u]

Yes. SCCs are cyclic.

[@hardikagarwal7652]

I don't get why the first DFS was needed?

[@gourharisharma9373]

so that you could store elements in stack, because after reversing the edges you cannot go from one component to another so stack will help you to find the node of next component.

[@yelnil]

Does it matter which node we start doing DFS during the first DFS?

[@techdose4u]

No. Because you can do manual jumps in DFS1 as well.

[@kirtigera2225]

thankew sir....

[@techdose4u]

Welcome :)

[@khilanpatels]

which software are you using to draw?

[@NoReelOnlyReal]

Explanation is very clear and understandable , altoghuh I had a question , can't we run the DFS on the original graph from last vertex and find the storongly connected components in each iteration ?

[@techdose4u]

Nope.

[@spatil689]

​@@techdose4u why?