# Modernization Hub

## Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm

Hello friends my name is Tushar and
today I’m going to talk about how to find strongly connected component using
Kosaraju’s Algorithm. So what is strongly connected component?
So here I have a directed graph and a strongly connected component in a
directed graph is a compliment such that all the vertices in that component is
reachable from every other vertex in that components. So here I have 4
different strongly connected components.1 of them is a ABC so A is reachable both
from B and C and C is reachable both from A and B and B is reachable both from A and C.
Similarly DEF is a strongly connected component, GHIJ is a strongly connected
component and then K is a strongly connected component. So what are possible
applications of strongly connected connected component. One of them could be
would be using this algorithm to find all the strongly connected people
with each other and then could be looking for common interests or
something like that in that component. So how do we find strongly connected
component. There are couple of algorithm to find it. One of them is
Kosaraju algorithm which we are going to discuss today. It’s a 2 pass algorithm
Basically it goes through this graph 2 times. So in the next section let’s see how
this algorithm works, why it works and then we’ll in the end look at the code
As I said it’s a 2-pass algorithm. So let’s see what we do in the 1st pass.
So we do a DFS on this graph and then we order the vertices of this graph by
finish times in decreasing order. So we need 2 data structures, a set to keep track
of all the vertices we have visited and a stack to order the vertices by
finish time. So we can start from any vertex. Let’s say we start from B. So
we, first thing we do is we put B in visited. Then we explore the
children of B. So B, let’s say go to C so C is not in visited so we go to C
put C in visited. Then explore the children
of C so there’s only one child A and A is not in visited so we put A in visited
and then explore children of A and that’s B but B is already in the visited. So we
don’t go to B. So at this point we have we’re done visiting all the children of A so,
which means that there is, A is done,A is finished. So A is the first vertex
to finish. So let’s put that in stack. Then go back in recursion and go to C and
C has no other children so C is done so we’re totally done visiting C. So
we push, we push C into the stack. Then we come to B and then B has
another child D so we go in the direction of D and D is not in visited so we’ll
put D in visited. Then D has another child E and E is not in visited so we’ll put E
in visited and then E has another child F and F is not in visited so we’ll
put F in visited and then F has child d but D is already visited so we go back
to F. F has no more children to be explored so we’ll put F into this stack and then we go
back to E and then E has no more children to be explored So we put E
into this stack and then we go back to D and then D has no more children to be
explored so we put D into the stack and from D we go back to B. So at this point B
has explored all its children. So we’ll put B into this stack. Then, then we pick another vertex
which has not been visited. So let’s say we picked I. So I is not visited so first
thing we do is we put I in visited. Then we explore children of I. So there’s only
one child of I, that’s J and J is not visited so we’ll put J in visited and then
we’ll explore children of J so let’s say K and K is not visited so we’ll
put K in visited and then K has no more children. So K is done. So we’ll put
K into stack and then we go back to J and J has another child G so we go to G,
put G in visited and then G has another child F but F is already visited so we’ll
do nothing. At this point J has another child H. So we’ll go in the director of
H, put H into stack and then H has a child I but I is already
visited so we’ll not go there so at this point H is done visiting
all its children so we’ll put H into stack. Then we’ll go back to G. G has done visiting
all its children so we’ll put G into stack Then we’ll go back to J and J has done
visiting all its children so we put J into stack and then finally we put I
into this stack. So this is the first pass of this algorithm and I have this
stack in which the vertices are ordered by finish time in decreasing
order basically the vertex which finished last for example I is at the top of the stack
and the vertex which finished first for example which in this example was A which is at the
bottom of the stack. So next let’s see how we do the second pass. So first thing I
did was I reversed my graph then in the second second pass I’m going to pop elements out
of this stack and do a DFS on this reversed graph. So let’s pop out I
and since I is not visited I put I in visited and this is my first strongly
connected component starting with I. So from I, I go to H so H is not in the visited
so we’ll put H in visited and then also add H as a part of this strongly
connected component and from H we go to G and G is not in visited so put it in
visited and add it as a part of strongly connected component and from
G, I go to J, J is not in visited so add there and add it here and from J we go to I but
I is already visited so J has no more children to be explored, G has no more children to be
explored I has no, H has no more children to be explored
and then I has no more children to be explored So basically we are done exploring all
the nodes from, vertices from I so basically this is our first component.
So at this point we’re going to go back into stack and pop out the next
element but this,this strongly connected component, the first strongly connected component is done. So then I pop out J but J is already part of
visited so I do nothing. Then I pop out G. G is already part of visited so I do nothing.
Then I pop out H, H is already part of visited so I do nothing. Then I pop out
K. K is not in visited so I add K here then I start the DFS from K. So this is
start of our 2nd component,strongly connected component. From K we can go to J but J is
already in visited so we come back to K and then K has no other child to
be explored in this graph so this this second stronly connected
component is just one vertex. So at this point we’ll go again into this stack and pop
out next element so that’s B so B is not in visited so I’m going to add it in the
visited and this is going to start my third component. So from B i can go to
A. So A is not in visited so I add here and then I add it here and then
from A I go to C. C is not in visited so I add it here and then I add it here
from C I can go back to B but B is already in visited so I go back to A. A
has no other children and then B has no other children so at this point we are done
exploring all the vertices vertices of this strongly connected
component. So then we’re going to start the next component. So we pop out D. D is
not in the visited so we add it here and we’ll start a new component here D and D has a
children F and F is not visited so we add F here and add F here
and then F has a child E and E is not in visited so we add E here and then we add E here
and then E has a child D but D is already in visited so we go back to E and
E has no other child and F has no other and D has no other child so this is
the 4th component and D has, D has another child B but B is already visited so
we’ll not go there So this is it. So D,so this is DFE is our
4th strongly connected component. Then I’m going to pop out E but E is already
visited then I’m going to pop F and F is already visiteded and then I’m going
to pop out C and C is already visited and then I’m going to pop A and A is already
in visited. So these are our 4 strongly connected components. IHGJ, K, BAC and then DFE. So let’s
analyze the time complexity and space complexity. So the, time complexity is
we did, in the the first pass we did the DFS so that will take O(E+V) time where E is number
of edges and V is the total number of vertices and then we reversed this graph and that
will take another (E+V) time probably depending on how the graph,how
you have represented your graph and then we did another pass on this,on
this graph, on the reversed graph and then we take another O(E+V) time. So the total time
complexity will be O(E+V). Space complexity is pretty
simple. The total number of elements in the stack
is total number of vertices and in the visited set is also total number of vertices.
So the space complexity is O(V). So in the next section let’s try to understand why
this algorithm works. CLRS book has a mathematical proof on why this algorithm works
but let’s see some intuition behind it. What I’m going to do is I’m going to
combine my vertices of a strongly connected component into one vertex and
create a new graph. So this ABC is one vertex and then DEF is one vertex
and then GHIJ is one vertex and then K is one vertex. Then
there’s an edge from this side of this strongly connected component to here
so we’ll create this edge. There’s an edge from here to here so we’ll create this
and then this. So what I’m saying is this graph is
guaranteed to be directed acyclic graph. Why? Because if there was a cycle here, for
example if there was this edge from here to here it means, for example there is an
edge from here to here. Then this combined
together would be 1 strongly connected component so we won’t have,we would not
have this edges as two different edge we won’t have this as 2 different
vertices but we would have this 1 combined vertex. The fact that we are
having this 2 different vertices it means that there is no cycle and it
means that this edge is not possible. So that shows why this is going to be a
directed acyclic graph. Now we did the ordering of vertices based on their
finish times. What that meant was that when all the children of, when all
children of a vertex are explored then put in a stack. So there’s a
guarantee that at least 1 vertex from this set is going to finish after this guy
because there’s an edge from here to here there’s a guarantee that there
will be at least 1 vertex here which will finish after all this guys are explorered. So let’s say that guy
was B. So in the, in the stack A and C went down then all this DEF goes on top of that
but at least 1 vertex from this set and let’s say that’s B will always fell on top
of this guy because there is a there’s a edge from this side to this
side. Similarly there’s a guarantee one vertex from here will finish
after all these guys are explored. Let’s say that guy was G so and then there’s
also guaranteed at least one vertex here will finish after K and let’s say
that guy was G. So then what we did was we reversed this graph. So when we reversed this graph this
will pretty much end up looking something
here will finish after K and let’s say
that guy was G. So then what we did was we reversed this graph. So when we reversed this graph this
will pretty much end up looking something like this. So by reversing this doesn’t
change because all the vertices are vertices are reachable from each other. They’re continue to be, they
will continue to be reachable from each other because it’s strongly connected component. Similarly
for these other strongly connected component. But this vertex this edge will have a different direction now
because we reverse this direction. So then what we did was we did a DFS based on
the finish time so what we, what guarantee we had was that B and G will
be picked before this, any of the vertex here or any of this vertex here is
picked. So when B got picked first we explored everything here so ABC got
explored and then we and then we finished and B could not explore anything here
because this, this, there’s an edge from this side to this side and then when G
got selected next G explored everything here so GHIJ and then by the time
K got selected or any of the edges any of the vertices in this group got
selected these 2 guys, all the vertices in this were guaranteed to be
explorer which is why when DEF got selected DEF could not explore,explore
any further because all these guys were already explored by either B or G and
similarly when K got selected K could not explore further because these guys were
guaranteed to be explored before K got selected. So that is how we ended up
having four different strongly connected components. Hopefully this gives you some intuition
why this algorithm works. Anyways as I said CLRS book has the full explanation
of the proof. So in the next section let’s quickly look at code for this algorithm. So we’re going
find strongly connected components. So my main function is scc which takes a graph and
then it returns a list which is a list of set where each set represents a
strongly connected component consisting of vertices. So first I initialize the
stack and then I initialize a set. So what I’m going to do is in the first pass is go through all the vertices, do a
DFS and order the vertices by the finish time in decreasing order. So let’s
say we start from vertex 2. So visited doesn’t contains 2 so we go into this
DFSUtil with 2 as the vertex so the DFSUtil is a very simple function. All it
does, it does a DFS and puts the vertex in a stack when it’s done exploring all
its neighbors. So we go, we start with 2 we add 2 to visited. Then we explore
neighbors of 2 so we get 3.3 is not visited so we call DFSUtil with 3,add 3 to
visited and then explore neighbours of 3 so let’s say we get 1.1 is not
in visited so we go into DFSUtil with 1 so we add one to visited and
then explore neighbors of 1 so we get 2.2 is in visited so we continue and then
there is no more neighbors of 1 to be explored so we add 1 to the stack. Then
we go back in recursion,go back to 3,explore another neighbour of 3
that’s 5.5 is not in visited so we add 5 to visited then explore neighbour of 5
which is 6 so 6 is not in visited so we add 6 to visited and then explore neighnour of
6 which is 4.4 is not in visited so we add 4 to visited and then explore number 4.4,
his neighbor is 5 which is in visited so we continue and so we’re done
exploring all the neighbors of 4. So at this time we add 4 to the stack and we
roll back in recursion where 6 was the vertex and 6 has no more neighbours to
be explored so we add 6 to the stack and then we roll back in recursion and
then add 5 to the stack and then come back to 3 and 3 has no more neighbours to
be explored so we add 3 to stack and then come back to 2 and 2 has no more neighbours to
be explored so we add 2 to the stack. Then we go back to the top our main function and then we explore
another vertex which has not yet been added to the visited so that vertex is
7 so we again call DFSUtil with 7 and add 7 to visited. Then
explore neighbours of 7 that’s 6.6 already is in visited so we don’t
go into recursion with 6 and then at this point 7 doesn’t have any more
neighbours to be explored so we add 7 to the stack. and then we go back to the top of, to
the main function. So at this point we have populated this stack and with the
with the vertices in a finished time in decreasing order. So next let’s reverse
the graph and do the second pass.So I reversed this graph and then I’m going to
do a DFS on this graph based of the vertices coming out of this stack. So
we cleared our visited set and then I create my result list where I’m going to
store all the strongly connected components. So while stack is not empty I poll out the first element, first vertex from
this stack. So 7 comes out of the stack and then we do a DFS on 7 so visited
doesn’t contain 7 so we create a new set for storing this strongly connected
component and go into this recursion DFSUtil for reversed graph. So in DFSUtil
for reversed graph first thing I do is I add 7 to visited then I add 7 to a set and
then I explore neighbours of 7.7 doesn’t have any neighbour in this reversed graph
so we do nothing and we go back to our main function and then in here we add this
set to our results list. So this is the first set in my list. Then I go back here
while stack is still not empty so I pop the next element out of the
stack and that’s 2 and visited doesn’t contain 2 so we create a new
set and then again call this DFSUtil
for reversed graph and in here first thing I do is I add 2 to visited and then
I had 2 into this new set and then I explore neighbors of 2 so first
neighbor I get is 1 so 1 is not in visited so we called DFSUtilForReversedGraph for
1. So first thing we do is we add 1 to visited and then add 1 to the same
set as we added 2 and then explore neighbours of 1 so that’s 3. 3 is
again not in visited so we again call this DFSUtilForReversedGraph add 3 to
visited and add 3 to this set and then 3 has a neighnour 2 which is already visited so
we roll back in recursion, go back to 1.1 doesn’t have anymore neighbour so
we go back to 2 and then 2 has no more neighbours so we’ll go back to the
top of this main function. In here we add this (2,1,3) set to our result and then we
pop out the next element from this stack so that’s 3.3 is already visited so we do
nothing about 3.Then we pop out the next element from the stack and that’s 5
So 5 is not in visited so we create a new set and then we again go into the
recursion with 5 so we come here,we add 5 to visited then we add 5 to
this set and then explore neighbours of 5. So the first neighbour of 5 is 3 but
3 is already visited so we do nothing about it so then the next
neighbor of 5 is 4 so 4 is not visited so we go into the recursion for 4.So
we add 4 to visited and add 4 here and then 4 has a neighbor 6,so and
6 is not visited so we put 6 in visited and add 6 here and then 6
has neighbor 5 which is already visited so we do nothing and then 6 has another
neighbour 7 which is also visited so we do nothing and then
we’re done exploring all neighbours of 6 so we go back to 4 and then we’re
done exploring all neighbours of 4 so we go back to 5 and then we’re done
exploring all neighbours of 5 so we go back to the top of this,this main
function. In here we add this set to the result and then we explore,we explore
the next,next element from the stack so that’s 6.6 is already visited so we do
nothing and then we poll the next element from this stack so that’s 4, it’s
already visited and then 1 is also already visited. So this is our this is our strongly connected
components 7,213 and 546. Again the run time complexity is O(E+V)
and the space complexity is O(V). So that’s all I have to talk about strongly
to the code is in the description section of the video. Thanks again for
watching this video.

### 100 comments on “Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm”

1. raghawendra singh says:

very well explained !!!!!

2. john cena says:

Here in your example G and I are not connected. then how g,h,i and j are strongly connected?

3. Vincent Townsend says:

Great

4. peaceandpiesperson says:

I am sorry, couldn't quite catch the name of the book … what is the book's name ??

5. Mehul Bhatt says:

what do you mean by "decreasing order of finishing time", when inserting nodes in the stack during the first pass?

6. rajiiiv123 says:

At some point, the learning stops and the pain begins.

Awesome explanation..
here is the C++ Implementation
http://www.binarycoder.org/data-structure/strongly-connected-components-graph/

8. Vishnu Viswanath says:

great video, could you also make a video about finding clique in a graph, I couldn't find any good video in youtube yet and your videos are very easy to understand. thanks!

9. Mary Rogers says:

Nice Video, very simple easily instruction of a complex problem

10. Jun Zeng says:

clear illustration. all your videos are so awesome. thank you for your effort

11. Emily Xie says:

This is beautifully explained. I was struggling to find an intuitive explanation for why this algorithm works until I found this video. Thank you!

12. Kabir Sahni says:

Keep up the good work!

13. Kriths Jeenu says:

awesome explanation!! Thank you so much

14. Pavan Bansal says:

superb explanation!!!

15. Ravi Rahul says:

sir please make a video for biconnected components also….this was a nice explanation!!

16. Jacky Ting Fai Cheung says:

your way is hard to tracking back……..but it's clear thanks

17. Francis says:

Fantastic explanation. Congratulations!

18. Ritu Agrawal says:

Very well explained. Thanks

19. 陳昱忻 says:

thanks a lot. ?

20. Amin Miri says:

Clear and worth watching (y)

21. CRis 07 says:

great explanation sir.thanks 🙂

22. Wei Xing says:

Thank you!

23. varun kunchakuri says:

can we say that the first pass is like topological sort implementation except the fact that topological sort cannot be applied on the cyclic graphs?

24. Zach B says:

Great explanation, thanks buddy!

25. Jayesh Tambe says:

+Tushar Roy : How about directions of edges of those strongly connected components? How do I represent that as a graph?

26. Netherblood says:

You are the best man

27. newworldorder25 says:

Very nice explanation of the intuition.

"By intuition that we discover and by logic that we prove" – Henri Poincaré

28. Sagar Kumar says:

Thanks Sir, For such a great explanation.

29. Daniel Marcu says:

great work

30. Matthew Sparrow says:

Children is already plural. You don't need to say childrens. Also, this video was dank af thanks bro, gonna ace my exam tomorrow. Let's smoke some hash soon my dude

31. vatsal agrawal says:

good tutorial sir 🙂

32. Mohit Gouniyal says:

please do something for subtitles because they cover screen.

33. HarisH SURYA says:

I was stuck at this topic for an hour or so. Thank you for explaining with an example. Not only it was so easy to understand, no i believe that i can teach it somebody else too.

34. Ali Asgar says:

Awesome explanation !!

35. Mohd Shariq says:

your accent is not good man.make it clear

36. NIKHIL SRIVASTAVA (B16CS020) says:

He makes it look so simple!
Hats-off to him 🙂

37. Deepansh Parmani says:

wonderful explanation especially the intuition part. can you make a video on <a href = "https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" > algorithm </a>

what do you mean by Strongly Connected Component? ..aapke papa samjhayenge

39. Effy Feng says:

excellent !!!!!!!!!!!!!!!!!!!!!!!!!!!!! amazing to have you in youtube!!!!

40. Hoài Phạm Đức says:

Very good explaination, thank you Roy

41. Kun Chen says:

very clear and smart explanation

42. PAVAN BHAVIRISETTY says:

nice explanation especially why the algorithm works

43. sushmita nigam says:

awesome

44. Arjun Krishna says:

great explanation

45. Indrajit Rajtilak says:

How do you ensure you've covered the entire graph in the first pass? We will have to do a set different b/w seen and the total graph and restart if it is non-zero – right?

46. Thiago Alexandre Nakao says:

Thank you so much!

47. Debraj Ray says:

Awesome explanation Tushar! Thank you 🙂

48. Nitish Gupta says:

Great explanation! Thank you so much!!

49. Erwin Clever says:

Thanks you very much

50. YourFather says:

Dude, you are awesome,
You finished all my doubts that came into my mind sequentially while watching this video.
Hats off /

51. Abhishek Anand says:

Nice Explanation

52. potatochip says:

Thank you very much, this was really helpful! Good job! 😀

53. Matt Mueller says:

just what I needed – thanks bud!

54. Aparichit Singh says:

sir can you please upload a video on strongly connected components using tarzan's algorithm!

55. SJ Shohag says:

thats cool

56. Rohith Y says:

the stack essentially contains the topological ordering of the graph right?

57. Samanvay Kumar says:

People with upper arm hair turn out to be rapists.. JK…good tutorial

58. Priya Kulkarni says:

Thank you.

59. Ma Yue says:

legend

60. wskenny says:

Perfect

61. spoorthi sm says:

Iam sorry sir. I failed to understand ur explanation in first move. Its little bit confusing.

62. Robbebeest says:

What an amazing explanation. Thank you very much!

63. Lalit Verma says:

useful but please use normal english as your 'staaack" hits in ear

aint no better explanation than this

65. Mehedi Sarwar says:

Wonderfully explained. A lot to learn from you. Keep up the good works.

66. praveen chaudhary says:

Great job. Whenever I search any algo on YouTube I search for your videos first. You explain everything simply and quickly.

67. kavi kavitha says:

Turshar…Please remove the background of the subtitles… its disturbing to see what you are writing on bottom of the board…

68. Ri Xu says:

I have watched all your videos about the algorithm, that's awesome!! really helped with my review and restudy!!! thank you so much 🙂

69. Thiago Oliveira says:

Great work! Thanks for putting up this awesome video! It really helped my studies.

70. Megan Lee says:

11:20 intuition on why the algorithm works

71. Antisocial Maity says:

nice explained sir….

72. Rodrigo Licata says:

Thank you!

73. NITIN JAIN says:

adbhut avishwaniya .. itna accha explanation .. bahut kam hi dekhne milta hai …
great tushar bhai ! !

74. Gitesh Khanna says:

Amazing intuition provided!

75. Yeetesh Pulstya says:

fucking brilliant man!

76. Shrinidhi Anil Varna says:

how to learn to code graphs easily? i feel they are above my limitations : (

77. mahdi mohebbian says:

absolutely perfect explanation!

78. Novin Shahroudi says:

at 9:09 from vertice D we should check B first, then F if we traverse lexicographically!

79. Mian Amir says:

Sir how to find cn chain by an edge

80. Алексей Белоус says:

thanks

81. Dan Samarasinghe says:

surprisingly a good explanation.thanks!

82. Abhishek ujjwal says:

It will be better to remove subtitle
Because it covers some part written on board

83. kenneth kho says:

Can you make the tutorial for tarjan's algorithm?

84. Anonyme Anonymität says:

Good job! Thank ya!

85. Aman Kumar Kashyap says:

But why this solution works?

86. Peanutology Institute says:

I want to make sure I understand you correctly @13:10, originally you considered the SCCs
B G
[ABC] –> [DEF] <– [GHIJ] —> [K]

"There is a guarantee that at least one vertex (say B) in [ABC] which will finish after all vertices in [DEF] have been explored"
@13:34 you say
"all this DEF goes on top of that but at least one vertex from [ABC] (say B) will always be on top of [DEF]"
I believe you meant to say "below of [DEF]", since if B is guaranteed to finish after all vertices in [DEF], B must be below vertices in [DEF]. Please verify.

87. Blue Acid says:

Wonderful!!! you helped me a lot, thanks!!!

88. Xin Li says:

The first pass is a topological sort right?

89. kislaya singh says:

Thanks a lot for great explanation.

90. Raffælmito says:

Thank you 😉

91. Syasya awesome says:

is cycle considered strongly connected then? what is the difference between a cycle and a strongly connected graph? And.. is that graph considered acyclic or cyclic since there are multiple cycles in it. I know you said the graph is acyclic but how come? what about the three cycles in it? (ABC & DEF & GHIJ ). Please help answer my questions as I'm super curious to find out. 🙂

92. Marcelo Santos says:

thanks man, your class helped me a lot

93. Sanmaro says:

thank you what a high quality works

94. Arun Varghese says:

from 14:00 to 16:00 its the fruit of logical reasonng

95. Ritik says:

banjau tera chela mujhe boht kuch sikhaana hai teri DSAlgo ki knowledge dekhke meri bndi bole mujhe isshi se DSAlgo sikhne jaana hai.

96. Shrey Jain says:

Kosaraju was an Indian.
Hit like if you didn't know this before.
Proud Indian

97. pale says:

very nice

98. Abhijeet Jha says:

just speak naturally !!

99. Luca Gallucci says:

Perfect explanation step by step. Good job ?

100. Shashank Kumar says:

Very well explained, bro. Did a nice job.