Tarjan's Strongly Connected Component (SCC) Algorithm (UPDATED) | Graph Theory 

This series of algorithm explanation is really awesome and helpful!

I'm not a native English speaker, your English is slow and clear, very nice video :), learn algorithm and your English pronunciation

Images speak more than the words. How Beautifully you explain such a compelling algo. Thank you!!.

Thank you! I watched like 5 other videos that all missed calling "only set the low if the node was on the stack" and it confused the heck out of me. Thanks again.

By far the most succinct explanation of Tarjan's SCC algorithm, thanks!

Finally, a well explained video of Tarjan's algorithm.

did not Tarjan lived in the jungle.

1. To update node u's low-link value to node v's low-link value there has to be a path of edges from u to v. U -> V 2. Node v must be on the stack. V -> U So, 2nd point actually mean there has to be a path also from node v to node u. And we can update u''s low-link value from v's low-link value.

So , basically a cycle is strongly connected component and tarjan saw this opportunity to make one more algorithm out of this. It is just glorious form of cycle detection in a directed graph. where we are keeping track of all the cycle

I just love the way you explain everything and make it easy to understand. Kudos to that!

Thanks a lot... This is a wonderful video. Possible Correction in the code: if(onStack[to]): low[at] = min(lo[at], lo[to]) The above statement would never run as after recovering from any dfs call, once the SCC gets identified, you've already popped off the entire stack. Safely enough, we've already assigned the lo-values to all nodes of connected componenets just when we identified an SCC.

incredibly well explained, you're trully talented at this, keep up the good work!

Just to drop this! Great

Your channel deserves much more views ! Subscribed !

This is pretty much exactly what I needed. Thanks for the well made explanation. :)

This is one of the best video on Tarjan's Algorithm . Thanks alot !!! 😄

Thank you so much for this, all your videos make these concepts so much easier and clearer to understand!

Best video on RU-vid for Tarjan's Algo

Love your way of explaining algorithm concepts

Hey, I wanted to know why we update the value of low a second time when we pop elements off the stack? It feels redundant to me

This is a great explanation!

Clear and awesome!

my teacher took 1.5 h to explain this concept and explained it in 9 min ( after playing it at 2x speed😉). Thank you

why did you remove your bridges and articulation points video ? you kept the older version of this. awesome series though !

great visuals! beautiful algorithm

I was curious why 16:32 set `low[node] = ids[at]` until i realized the counterexample 0 -> 1 1 -> 0, 2 2 -> 1 then assume we DFSed 0, 1, 2... it turns out that unless we fix the low[node] at the end 2 would have a lowlink of 1. try it!

This was an amazing explanation! I have one question though: in dfs function, @16:51, is `low[node] = ids[at]` line inside the stack-pop for-loop actually necessary? It seems to me that the low[node] should be properly set everytime a node is called back.

This was a beautifully written explanation. Thank you! Awesome dedication to helping the viewer understand rather than "look what a l33t h4x0r i am"

Great explanation. Thanks William

I just love your content! 🙌

an excellent explanation, thanks a lot.

Hey, thanks a lot for your videos! Is it necessary to assign low[node] = ids[at] while popping the stack (at the end of dfs function)?

thank you so much, watched this just in time!

awesome explanation. but in the pseudo code, when i replace low[at] value with min(low[at], low[to]) why do i again need to carry out low[node] = ids[at] while removing from the stack ? also, i found a similar code somewhere else with a minor difference which is min(low[at], ids[to]) instead of min(low[at], low[to]). please clarify the doubts...thanks in adv

You are the goat brother! 🐐

Great video, thank you for the explanations

Low-link , is not smalest node id reachable from node i , its smalest node that's can reach just using one back-edge in DFS tree

Keep on making helping a lot, you are bringing change!!! thanks man

It took some time to understand, your video helped

Many thanks for the very clear video! What about a video on a closely-connected (yes😏) algorithm to find all cycles in a directed graph, namely Johnson's algorithm?

Incredibly helpful.

for the code, in the visiting neighbor step, you shouldn't be able to do onStack on the previous node. This will cause the entire thing to fail fix is to skip the iteration if the neighbor node is the previous node.

Thts a indepth Easy Explanation of a Complex Algorithm ,

can this algorithm be detected nest SCC? for example at 1:10 the red circle (0) -> above the purple circle -> next purple circle -> -> below the purple circle --> red circle (1). Now we have 2 SCCs, one is 3 purple circle and bigger SCCs is 3 purple + red.

That was a great explanation! Thanks!

Very comprehensive!

Wouldn't 16:19 be cleaner with a while loop?

thanks for a super clear example

Very nice explanation. Thank you

Hey William did u take down your articulation point video? I couldn't find it on your playlist

Hey William! Great graph collection there, can you put videos on articulation points and bridges?

Hi William - this video was helpful, but can you include links to cycle detection in directed and undirected graphs? Tarjan's was much more intuitive after first understanding cycle detection in directed graphs via DFS. Also can you review the difference between weakly connected vs strongly connected in direct graphs - I think that would help.

Beautifully Explained :)

Very nice video, which editing software did you use to make the video William ?

Amazing explanation! Thanks!

Thank you very much, that was amazing!

Super Good Explanation!

Do I understand correctly that you explained to us that the effect of algorithm finding value of index is highly dependent on... indexing?

Can you make a video on the theme of the Feedback arc set? Your videos are very good!

Why we need stack data structure ? bool onStack[n] should just help ??? Please help me understand...

Very interesting video to learn from, thanks

very beneficial , Thank You

Awesome! Thank you!

amazing videos man!

Geat explanation. Thanks.

I don't understand what will be the run time and space complexity?

Thank you Sir

Loved it

hi, why does the algo ensure low[node] after popping from stack? does this line low[at] = id++ not guarantee that?

at 16:45 we are setting low[node] to ids[at] would it not have already happened above when low[at] = min(low[at], low[to]) this seems redundant. what am I missing??

Cool as ever.

Thank you so much for the content. Would you consider removing the old content? I was watching it, and noticed what might be the issue with it, but for a while I thought I missed something until I read the comment. Also, is there any relation between two different SCCs?

Is low[node] = ids[at] necessary? Yes: Consider this graph with 4 nodes [1,2,3,4] and edges 1->2, 2->3, 3->2, 3->4, 4->1 1 -> 2 -> 3 -> 2 (cycle 3 -> 2 -> 3) 3 -> 4 -> 1 (cycle 3 -> 4 -> 1-> 2 -> 3 The whole thing is one SCC. if the dfs goes from 1 -> 2 -> 3 -> 2 (backtrack and assign low[3] = 2, low[2] = 2) and then backtrack to 3 -> 4 -> 1 (backtrack and assign low[4] = 1, low[3] = 1, low[1] = 1 We see low[2] is left forgotten to 2 if we don't add the low[node] = ids[at] line. This will identify SCC1 = [1,3,4] and SCC2 = [2] which would be wrong.

Thanks!

Good Idea, to separate the Lowlink-calculation from the Rest!

this really helps. thx

Thanks for this video :)

I saw an another video by you which explains how to find bridges and articulation points. Can you tell me why tarjan's algorithm is needed and in what cases your previous algorithm for finding bridges and articulation points does not work?

Why did we use DFS here and not BFS? (I kinda know we have to reach all possible paths from a node still looking for some structured reason) Thanks in advance!

Is the low[nodes] = ids[at] necessary?

Thanks

Anyone knows of any problems on LC that relies on finding SCCs? 1319 is connected components, but can't find a question for SCC.

super!

Awesome

Thank you for your clear explanation and awesome animation. I have one question though: I came across the pseudocode of this algorithm on Wikipedia: en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#The_algorithm_in_pseudocode It seems that they update the low link value differently: if ( ids[to] == VISITED) { dfs(...); low[at] = min(low[at], low[to]); } else if (onStack[to]) { low[at] = min(low[at], ids[to]); } Wikipedia even said that when to is onStack, updating low[at] as min of low[at] and ids[to] is deliberate (ids[to], not low[to]). I'm just wondering if this is needed or your code has covered this case? Thank you.

Thanks you~!

I think there is some issue with the implementation of the algorithm presented here. I tried to dry-run this algorithm on graph shown at timestamp 07:16 in ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-aZXi1unBdJA.html Draw above graph on a paper and follow below steps, (Delete/ignore node 3 and node 4 from graph) If you start dfs from node 0, it may run like this, 0 -> 1 -> 2 When running dfs at node 2, it may look at node 0 first(which is already visited) and, we will update node 2's low[2] to 0. Why, because node 0 is in stack and, even if the node we are looking at is already visited, we are still updating low[at] to min(low[at], low[to]) and here, low[to] is low[0] which is 0. Remember that we have initialized low[2] to 0. Let us continue the dfs for node 2, 0 -> 1 -> 2 -> 5 -> 6 -> 7 -> 8 At node 8, if dfs looks at node 2(already visited), we will still initialize low[8] to min(low[8], low[2]). Here low[2] is 0 and is minimum of the two so, low[8] is initialized to 0. Looking to node 5(already visited) will not change anything. Now, we have initialized low[8] = 0 (Doesn't this look wrong?) If dfs backtracks(node 8 doesn't have any more unvisited neighbors) like, 0 -> 1 -> 2 -> 5 -> 6 -> 7 -> 8 ---Backtrack starts---> 8 -> 7-> 6 -> 5 -> 2 -> 1 -> 0 During backtracking, low[8], low[7], low[6], low[5], low[2], low[1], all are initialized to 0. This gives the entire graph as SCC. Isn't it incorrect or am I missing something here ? Edit : After checking wiki, I'm pretty sure if(ids[to] == UNVISITED) : dfs(to) if(onStack[to]): low[at] = min(low[at], low[to]) is incorrect. It should be modified to, if(ids[to] == UNVISITED) : dfs(to) low[at] = min(low[at], low[to]) if(onStack[to]): low[at] = min(low[at], ids[to])

can you use tarjan to find articulation points?

Can we have Johnson's elementary cycles algorithm?

whats if node 0 was not visited when we reached 5?

In a cycle of a graph only the end and start vertex is repeated. If you have, for instance, a graph containing the cycles 1 -> 2 -> 3 -> 1 and 2 -> 4 -> 2, then 1,2,3,4 form a SCC but *not* a cycle. So the thinking of self-contained cycles is a bit misleading/confusing here. Your example, in the beginning, is a special case where such SCCs do not appear.

ORZ🔥🔥🔥🔥🔥

Good explanation. How do you extrapolate this to finding critical connections in a graph ?

what do you mean by lowest node id?

Beautiful explanation. One question however, when there is no SSC in the graph (like a simple one - directional chain, ie. A -> B -> C -> D) , then it can clearly be seen that sscCount will not be 0. Isn't that misleading? Or, what does that tell us?

Hey, are you active on some media. Would love to talk!

*scratches head* What is this sorcery?

He sounds like ParashockX

Isn't low link value of a node _v_ the smallest "id" of a node that is reachable from _v_ via a path of tree edges followed by _at_ _most_ _one_ _non_ _tree_ _edge_ ?

why is node 4 at this location ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-wUgWX0nc4NY.html not having the low-link value of 0 and why is it a 4? I am still finding this "low-link" concept hard to understand