G-54. Strongly Connected Components - Kosaraju's Algorithm

GfG-Problem Link: bit.ly/3R6LzID
C++/Java/Codes and Notes Link: takeuforward.org/graph/strong...
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
---------------------------------------------------------------------------------------------------------------------------

[@adithyabhat4770]

Your videos and the SDE sheet are helping me so much to brush up the DSA concepts and learn the ones I ignored in college. A BIG THANK YOU!!

[@cinime]

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

[@kushagrasrivastava1443]

I thought I was done with graphs 😅

[@SomeshCodes]

Literally me too...😅

[@andreasleonidou3620]

Excellent tutorial and really helpful, thanks!!

[@muskanchaurasia1532]

Just amazing. Great Explanation.

[@ShreyaLanka-1912]

Understood!! Thank you for this amazing explanation.

[@adebisisheriff159]

Honestly, this playlist deserves Millions views and comments..... Thanks for all you do Striver!!!

[@kritikarawat2180]

Man, amazing explaination. Hats off to you buddy

[@KaushalDhruw]

Finally understood kosaraju algo. Thank you striver.

[@user-oh9qm7pe8h]

The above code gave me `TLE` so, with few minor changes it will work for you. To optimize the given code, you can make a few changes to improve its efficiency: 1. Pass the `adj` vector as a reference to the `dfs` function: Currently, the `adj` vector is passed by value, which creates a copy of the vector in each recursive call. Instead, pass it by reference to avoid unnecessary copies. 2. Use a vector of vectors (`adjT`) instead of an array of vectors for the transpose graph: Declaring `vector adjT[V]` as a variable-length array may cause a stack overflow for large values of `V`. Instead, use a vector of vectors to represent the transpose graph (`adjT`). 3. Reserve memory for the transpose graph vectors: Before pushing elements into `adjT`, reserve memory for each vector based on the size of the corresponding adjacency list in the original graph. This avoids frequent reallocations and improves performance. 4. Use vectors instead of stacks: Instead of using a stack to store the finish times of the nodes in the first DFS, you can use a vector and append nodes at the end. This eliminates the need for reversing the stack later on. Here's the optimized code with these changes: Code : class Solution { private: void dfs(int node, vector& adj, vector& vis, vector& finishOrder) { vis[node] = 1; for (int it : adj[node]) { if (!vis[it]) { dfs(it, adj, vis, finishOrder); } } finishOrder.push_back(node); } void dfs2(int node, vector& adj, vector& vis) { vis[node] = 1; for (int it : adj[node]) { if (!vis[it]) { dfs2(it, adj, vis); } } } public: // Function to find the number of strongly connected components in the graph. int kosaraju(int V, vector& adj) { vector vis(V, 0); vector finishOrder; for (int i = 0; i < V; i++) { if (!vis[i]) { dfs(i, adj, vis, finishOrder); } } // Creating the transpose graph (adjT) vector adjT(V); for (int i = 0; i < V; i++) { vis[i] = 0; for (int it : adj[i]) { adjT[it].push_back(i); } } // Last DFS using the finish order int scc = 0; for (int i = V - 1; i >= 0; i--) { int node = finishOrder[i]; if (!vis[node]) { scc++; dfs2(node, adjT, vis); } } return scc; } }; These optimizations should improve the efficiency of the code.

[@HanumaVamsi2001]

Thanks a lot man!!

[@muditkhanna8164]

yeah that improves the code a lot!

[@khubanzehra7632]

Thank you so much

[@veekykumar4211]

great work sir i just watch ur few video and ur content is awesome

[@Mr_Cat_11]

Long time no see sir 😊 Thank you for posting 🥰🔥💖

[@bhavikpunmiya9641]

Thanks for Explaining this concept :) really liked your explaination

[@Emperor723]

mazaaaaaaa aaaaaaaagyaaaaaaaaaaa this is first time i have come across any of your videos der aaye par durust aaye.... let me subscribe!

[@rohinianekar61]

understood, nice explanation

[@AmanKumar-wd2mq]

You explain so well ❤❤

[@dishant930]

I think after seeing the video if you read the striver sheet explanation for the same question it will give you more insight since it is really well written. I really liked it!

[@siddharth.chandani]

Can you provide me link of that..

[@nanireddy3606]

It is in the description

[@stith_pragya]

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

[@sahilbheke4083]

You are a very good teacher apse sikhna easy lagta hai

[@amitp277]

Awesome work 👏

[@augustinradjou3909]

Going to end the graph..❤ understood

[@krishnavyaskondle5707]

Thanks for Explaining the logic

[@chandrachurmukherjeejucse5816]

And here comes the real OG Striver.❤

[@249abhi]

awesome explanation!

[@devanshubilthare5277]

Amazing content🔥

[@sauravchandra10]

Understood, thanks!

[@rahulsangvikar7973]

Just realised one thing. You can avoid reversing the graph if you were to put the time in a queue instead of a stack.

[@reee896]

No you need stack cause if you use Queue it will keep going on to next SSC using the visited araay

[@paruldamahe7969]

amazing content!

[@sukhpreetsingh5200]

Awesome thanks a lot

[@mathematics7746]

awsm explanation thank u so much

[@ritulraj6119]

🔥🔥🔥🔥 Explanation

[@parshchoradia9909]

Understood Sir!

[@UECAshutoshKumar]

Thank you sir 🙏

[@visheshagrawal8676]

amazing content

[@mohitsingh13]

Understood ❤

[@eswartharun3394]

This is much intutive than the previous video on kosaraju(other graph playlist)

[@takeUforward]

Yes I read the comments, and then made this one.

[@dhirendrasingh6071]

@@takeUforward you have changed the lives of so many students, you have blessings of many. ♥️

[@tanmaypal2003]

​@@takeUforward when we sort all the edges according to finishing time and store it in stack like this 0,1,2,3,4,5,6,7 , so instead of storing in stack can we use queue and then when we pop out elements from queue we start DFS from 7 instead of 0 and 7 is not connected to anyone so we found 1st SCC then we pop 6 and do DFS and found 2nd SCC then we pop 3 and do DFS and got 3rd SCC and so on. In this approach we don't need to reverse the graph. Can we do like this?

[@vishalsinghrajpurohit6037]

@@tanmaypal2003 Nice observation. I think this should work fine.

[@theSoberSobber]

@@tanmaypal2003 yes

[@GANESHSINGH-uc1gk]

crystal clear

[@oracle_ae]

Thanks buddy

[@divyareddy7622]

thank you very muchhh! You've literally changed so many lives ✌️

[@-VLaharika]

Understood 👍

[@herculean6748]

Thanks🙌

[@nitinkumar5974]

thanks for the video

[@suryakiran2970]

Understood❤

[@user-pr2ju2zf4q]

hey striver can we do bfs to sort the graph according to their finishing time ? is it possible ?

[@divyatejaswinivengada6368]

Understooddd!!

[@Kupo3.0]

Understood!

[@afraztanvir973]

Is there any relation in this algo and topo sort as we get reverse topo from stack

[@adamyasharma_0135]

amazing..

[@wilhelmrudolphfittig3577]

maza aaala re ala striver aala

[@Parthj426]

Understood after a little bit of effort.

[@piyushacharya7696]

reach++ Loved it

[@dumpster-jackson]

Understood!!

[@evilpollination1916]

Understood.

[@mraryanrajawat9693]

class Solution { private: void dfs(int node,vectoradj[],vector&vis,stack&st) // dfs for adj { vis[node]=1; for(auto it:adj[node]) { if(vis[it]==0) { dfs(it,adj,vis,st); } } st.push(node); } void dfs2(int node,vectoradjT[],vector&vis) // dfs for adjT { vis[node]=1; for(auto it:adjT[node]) { if(vis[it]==0) { dfs2(it,adjT,vis); } } } public: //Function to find number of strongly connected components in the graph. int kosaraju(int V, vector adj[]) { vectorvis(V,0); stackst; vector adjT[V]; // adj list after reversing edges for(int i=0;i

[@discuss1]

How do I pick the starting node for sorting. In the above example if we would have started sorting from Node 3, I would have never reached 0, 1, 2. So how to calculate this increasing time for all nodes efficiently.

[@ms-ej4gd]

Big fan of your work striver

[@h6_wingers]

mast padha dia bahiya

[@nisanduathsara5242]

understooood

[@rishabhjain6272]

the first step is same as topo sort using dfs technique, will not work with bfs (khann's algo) due to directed cyclic graphs.but if you apply topo sort using dfs in directed cyclic graphs ,it will work.

[@PalashAgrawalECE]

19:55 Why did you mention to write as private function. Is there any advantage of it over public. As I tested in run time and got public working faster than private. Also from outer source noone is calling that dfs function. So kindly elaborate please

[@manojnavinjamuri5867]

understood

[@abhinavbhardwaj3372]

understood sir

[@space_ace7710]

GFG compiler giving TLE, don't know why?? :(

[@LearnerForever123]

Understood

[@iKnowThatSong]

Instate on transposing the graph, can't we just start from the last node? someone please explain....

[@ManishKumar-zm9rj]

We can use the same dfs again by passing a dummy stack: public void dfs(ArrayList adj, int[] vis, Stack st, int node){ vis[node] = 1; for(int it : adj.get(node)){ if(vis[it] == 0){ dfs(adj, vis, st, it); } } st.push(node); } //Function to find number of strongly connected components in the graph. public int kosaraju(int V, ArrayList adj) { int[] vis = new int[V]; Stack st = new Stack(); for(int i = 0; i < V; i++){ if(vis[i] == 0){ dfs(adj, vis, st, i); } } ArrayList adjT = new ArrayList(); for(int i = 0; i < V; i++) adjT.add(new ArrayList()); for(int i = 0; i < V; i++){ vis[i] = 0; for(int it : adj.get(i)){ // previously: i -> it // Now make it: i i adjT.get(it).add(i); } } int scc = 0; while(!st.isEmpty()){ int node = st.pop(); if(vis[node] == 0){ scc++; dfs(adjT, vis, new Stack(), node); } } return scc; }

[@AryanMathur-gh6df]

UNDERSTOOD

[@anonymous-ws2ij]

Hey Striver.. I had a question.. If we store the nodes according to their finishing time in a queue and rather than reversing all the nodes can't we simply do tranversal from the nodes in the queue in the similar fashion as you did.

[@mayankgarg8103]

at 13:00 while traversing at scc1 from the node 0 using dfs you have taken the edges in the already present way(or say initial way) but since we have reversed the edges it should move in another way and you are also using the fact of of the edges being reversed at 13:05 when you are trying to access 3 from the dfs(2) you have said that . Then again same thing when doing same thing for dfs(3) we are not using the fact that edges are reversed. Can anyone here clear my doubt that where I am understanding it wrong?

[@iamnoob7593]

I get ur point , Striver used scc1->scc2->scc3->scc4 , Iniital config something like scc1scc3->scc4 can be used for better understanding

[@UjjawalPathak-qy3uj]

HEY STRIVER, We can also reduce the time and steps if first getting there there finishing time and store in a queue rather then stack so because of FIFO we know first element to finish so we don't need to reverse the graph either we can directly go through the finishing elements which are already reverse with respect to graph it will reduce steps and clean code too. correct me if I m wrong

[@KratosProton]

great

[@udaypratapsingh8923]

understood 🥶

[@p38_amankuldeep75]

understood💛💙💛

[@sathvikmalgikar2842]

guys just in case any one wondering why that stack of dfs calls was required that is only if u r solving for the second case of actually printing the components and not just finding number of components. like based on the stack trace u can make a note of elements while popping and put them into groups and print

[@vishalcheeti8374]

without using stack, how to do solve the first case of finding no. of compo? I mean to find no. of components also we need it in sorted way right?

[@durgeshjadhav01]

nice

[@muditkhanna8164]

please make videos on Eulerian paths also.

[@pavanrai6196]

Can't we use queue and then not reversing the edges and just count no of scc of back, but it's not working idk

[@DheerajDivaker]

edges ko reverse karne se SCCs separate ho rahe hai..

[@dhanashreegodase4445]

ultimate

[@dhruvn6522]

Sir is sorting edges according to finishing time same as topological sort?

[@discuss1]

Will topological sort work in cyclic graphs?

[@mr.dependable4885]

Why is it important to reverse the edges, can't we just start the dfs in reverse order ? Like in the example start from 7 can any1 please explain

[@arpitrajput6424]

we can't .try dryrun on 1st example , suppose u created vector which store the timing then timing will be {1 2 4 3 0} if you try dfs accoording to this you still cannot find scc.

[@shivamsangwan7268]

Yes, you can do that. But, this video is about Kosaraju's algorithm, which is implemented this way.

[@jaishriharivishnu]

Note: we can't say this as a Topological sort(as topological sort using DFS will get you stuck in Loop i.e cycle), but its a bit different. Its topological Sort for the SCC.

[@tanmaybro3812]

Isn't the first step same as topological sort?

[@danushbasanaboyina1306]

In the first step.sorting all the edges ...looks like topological sorting..... Is it the same I am thinking....

[@sahiljaiswal9270]

I am confused about the first step of arranging nodes on their finishing times. I thought that instead just doing normal DFS on reversed graph skipping the first step might also work but it doesnt, Can anyone explain this with an example

[@harshitpant07]

if you reversed the graph and then perform the dfs how will you be able to reach form[0,1,2] --> [3] so to tackle this we store them in a stack to remember their order form start to finish .

[@abcsumits]

sorting according to finish time can be done using toposort:)

[@deviprasad_bal]

that is toposort only. Toposort can be done using stack and that's what it is here.

[@DheerajDivaker]

@abcsumit Toposort banega hi nahi, wo sirf DAG mein work karta hai.

[@DheerajDivaker]

@@deviprasad_bal Toposort banega hi nahi, wo sirf DAG mein work karta hai.

[@Anonymous_Coder]

@@DheerajDivaker Yes you are right but here since graph can be cyclic as well as acyclic , so incase of CYCLIC one edge which is causing cycle is not stored , like 1->2->3->1 , is only stored as [ 1, 2 ,3 ] . So ultimately we should not call it as a toposort ,but implementation is exactly same.

[@DheerajDivaker]

@@Anonymous_Coder yes absolutely correct.

[@Rajat_maurya]

why we need to sort, why can't we simply use ? for(int i=0;i

[@jahanvichaudhary81]

same question

[@rahulsangvikar7973]

Sorting makes you sure that you process those nodes first which lie at the end of a directed path. If you apply it randomly, you might start dfs from the start node or any node in the middle and will visit the nodes that are not a part of the SCC as well.

[@ayushman_sr]

thought process is very tricky

[@adityavaste8963]

Can we skip the step 1, and just reverse all the edges ? Because after reversing edges, components will be logically separated and we can run DFS on it separately, and can find the nodes in each component. Please can anyone guide me on this ?

[@adityavaste8963]

Ohh, got it. It's for the efficiency

[@Jinxed192]

for eg, in the same example as striver's, if you reverse the edge between 2 & 3, with your process, when the graph is reversed, the dfs(0) has 3 as well in it, this is the loop hole. Whereas, in the algo, when we do dfs first and calculate finishing times, we get 3 at the top of the stack, so now we can make different dfs calls for each scc. Hope you understand. Have a great day!

[@adityavaste8963]

​@@Jinxed192 Thanks for explaination. That means we must know from where to start, to void futher conflicts.

[@sharathkumar8338]

Understood brother. Could you please upload videos on sliding window and 2 pointers?? I saw most amazon OA will be based on that only.

[@saitejadamaraju5408]

Already there in the channel bro

[@083_h_nitishkumarjha3]

can't we just use visited array to count the scc in reversed graph , similar to counting different components

[@DheerajDivaker]

starting vertex kon hoga, fir ye kaise pta lagaoge? jiska finishing time sabse jyada hoga wahi starting point hoga aur iske liye hume stack mein Finishing time ke according vertices rakhne padenge.

[@sandeepmourya8922]

isn't the timestamp same as toposort ? or there is any difference

[@DheerajDivaker]

Toposort possible in DAG only

[@sahilbheke4083]

codes not uploded

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉🎉

[@aktiwari3379]

♥️♥️✌️

[@vaibhavrawat4008]

wow

[@no---on]

In given example if we just make a little change with 3->2 then after reversing the edge will be 2->3 so in step 3 dfs call 2 will also go to 3 . I feel like it should not go to 3

[@abhishekchoudhary7030]

i have the same confusion that if we start with 7 in the start rather than 0 , we will get wrong connected components

[@amitp277]

👏👏

[@kanishkdadhich5354]

I have a small doubt related to a test case Suppose the graph's adjacency list is like ( Directed graph, u-->v) 0 1 1 3 3 4 4 1 2 1 There are 3 strongly connected components. But what will be the scc1 , scc2 and scc3 ? I am confused because in my test case the components are as follows:- comp1 ---> comp2

[@sanjana-singla]

It all works out at the end. If you solve the algorithm manually, you can find your doubt solved. Here is it you are given the edges list -> [[0,1],[1,3],[3,4],[4,1],[2,1]] adj Matrix will be -> [[1], [3], [1], [4], [1]] 0 , 1 , 2 , 3 , 4 dfs(0) dfs(2) | dfs(1) | dfs(3) | dfs(4) Stack will be -> 2 0 1 3 4| adjT will be -> [[],[0,2,4],[],[1],[3]] 0, 1 , 2 , 3 , 4 stack traversal will give us -> [2] [0] [1,4,3]

[@anishraj66]

bhaiya can,t we solve it by reversing the stack instead of reversing the graph

[@visheshagrawal8676]

stack reversal will reverse the finish time but reversing the graph does not allow us to go from one scc to another scc

[@PankajGupta-cx3ji]

choit💥💥💥