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

[@haocherhong]

This series of algorithm explanation is really awesome and helpful!

[@najimali32]

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

[@calvincruzada1016]

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

[@amirabdou4940]

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.

[@irulam4116]

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

[@angelzarate7480]

Great set of videos. My professor is good, but it is always nice to hear a second take on a problem. Helps consolidate especially with the visuals.

[@xiaoyao1593]

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

[@akshatshukla6617]

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

[@shreyasvishwakarma8979]

Best video on KZbin for Tarjan's Algo

[@buildsucceeded]

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.

[@brunoamezcua3112]

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

[@saifmohammed1481]

Your channel deserves much more views ! Subscribed !

[@shreyashachoudhary480]

Just to drop this! Great

[@r__e__x__]

This is a great explanation!

[@DanielGeri]

great visuals! beautiful algorithm

[@docstyagi7775]

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.

[@docstyagi7775]

Tell me if I'm wrong btw.

[@username-ur6dq]

This is old but you are wrong. If a node is a neighbour to another node we already visited, it may happen that we haven't searched all the neighbours of that node, and thus haven't poped it from the stack. which means that they are in the same SCC so we update accordingly the low link.

[@albertssj25]

Love your way of explaining algorithm concepts

[@Kaitn13]

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

[@sakethamargani8846]

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

[@aries3690]

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

[@frogfrogfrog12345]

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!

[@SRhyme]

Then why do we need to set low[at]=min(low[to],low[at]) ? The nodes in the stack should be eventually set to id of the starting node. Which is minimum. Can you explain?

[@cvjkctr]

@@SRhyme Well no if we dont set that then the value of the start node wont be propagated across the cycle. Each node will become its own SCC.

[@mehdisaffar]

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.

[@ANUJ-we3su]

even i have same question do u get the info regarding this ,this hould be written or not?

[@clementdumas6371]

@@ANUJ-we3su Yes it is, a good example is a directed square (1 SCC) with a triangle (starting from top left node) : o--o--o | | / o--o

[@introvertsinger710]

@@clementdumas6371 I still didn't get it, can you please elaborate ? I still think we don't need to set low[node] = ids[at], as they will be set corrected during dfs itself.

[@Ieatyou4ever]

A bit late to this party, but to answer your question - No, 'low[node] = ids[at]' is not needed because by the time you to the stack.pop loop, the lowlink values of the SCC members have already been set. Of course you can just debug a quick example and see for yourself :)

[@MiddleLock]

Great explanation. Thanks William

[@bharat_arora]

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

[@hil449]

This is much more complicated than just finding a cycle. In order to find a cycle you only need a color array with colors 0, 1 and 2. Tarjan algo requires this low link concept which is pretty ingenious

[@chenjason2598]

Clear and awesome!

[@ev.or.evgeny]

Thanks!

[@rj-nj3uk]

did not Tarjan lived in the jungle.

[@urvishmehta9019]

Jen is disappointed reading this

[@aerospace_andy]

thank you so much, watched this just in time!

[@DeepROde]

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)?

[@filippogarosi]

Good question, i also didn't get it

[@alextkach9854]

Same question!

[@waldtrautwald8499]

Yes, it's necessary because the low array will be the output of the algorithm. The low array is used as a kind of SCC identifier. If the condition "ids[at] == low[at]" is true, the current node is the start of a new SCC, which contains exactly the nodes that are currently on the stack (above and including the current node). This is why we assign each node on the stack the same low value. After the algorithm is finished, all nodes with the same low value are part of the same SCC. Edit: He also could have added "create a component" as the first line inside the "if" and replaced the "low[node] = ids[at]" with "add node to that component". This is essentially what's going on.

[@nameayeIIowfruit]

@@waldtrautwald8499 But the nodes that are part of that SCC should already have the same low value from the "if(onstack(to)): low[at] = min(low[at], low[to])" step or am I missing something?

[@nameayeIIowfruit]

@@waldtrautwald8499 Nevermind I found an example that shows the nodes of an SCC don't need to have the same low values before the "ids[at] == low[at]" step

[@bunggo9914]

an excellent explanation, thanks a lot.

[@markoruzak8475]

Incredibly helpful.

[@prajaktadharme2072]

That was a great explanation! Thanks!

[@shreyashachoudhary480]

I just love your content! 🙌

[@falkmuller232]

Very comprehensive!

[@SAMI-ds1rj]

Great video, thank you for the explanations

[@MrFirelord]

Thanks

[@muonline2067]

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.

[@abhinavsingh-zc2hk]

Beautifully Explained :)

[@rohitashwanigam]

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

[@JL-pg4pj]

thanks for a super clear example

[@CataRemixDj]

Amazing explanation! Thanks!

[@JaanJaan123123]

Very nice explanation. Thank you

[@pranjalsharma499]

It took some time to understand, your video helped

[@priyamomer1442]

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

[@saikumartadi8494]

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

[@saptarshiganguly1683]

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

[@MatthewLuigamma032]

Yeah, it seems to work without the low[node] = ids[at], at least when I ran it with the example from the video.

[@nameayeIIowfruit]

@@MatthewLuigamma032 It doesn't work for all examples tho

[@nameayeIIowfruit]

​@@MatthewLuigamma032 One example to show this: A->B B->D D->E->C E->A C->B If you start dfs at the A node the C node should have a low value of 1 while the others have a low value of 0 before the "low[node] = ids[at]" step

[@shouryasingh2193]

Thts a indepth Easy Explanation of a Complex Algorithm ,

[@libbyisakitteh]

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

[@timzeng9813]

Super Good Explanation!

[@amoghdadhich9318]

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

[@rishirajyadav3059]

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

[@ahmadmohamad8416]

very beneficial , Thank You

[@markoruzak8475]

Thank you very much, that was amazing!

[@toddchaney2454]

Very interesting video to learn from, thanks

[@anthonyguerrera191]

Not sure if this comment will be read, but had one question. Why is the line low[node] = ids[at] necessary when we are popping off of the stack? Is it not guaranteed that all nodes on the stack will have a low-link value equal to the minimum low-link value for that scc?

[@rizzbod]

amazing videos man!

[@GauravSharma01]

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

[@GauravSharma01]

got the case 0 -> [1], 1 -> [0, 2], 2 -> [1] here we have low link value to start will be [0, 1, 2] we start traverse from 0 and dfs to 1. at one we may do either of two ways 1. traverse to 0 then 1 2. traverse to 1 then 0 if it is 1st case then all is good 2 will also get a low link value of 0 in 2nd case 2 is traverse and marked low link value of 1 as 1 has low link value of 1 at that point. 1 will then traverse 0 later and get a low link value of 0 but it will not be propagated to 2 at that point. hence we will need to re assign low link values to stack once we come back to original node which we started with if it’s low link value is itself. to ensure we propagate low value correctly we would have to choose neighbour we already visited first which will increase the time complexity

[@jannesbikker]

You are the goat brother! 🐐

[@quangtuanle1631]

Awesome! Thank you!

[@victorwallin3149]

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

[@Fighter_Believer_Achiever]

Thank you very much!!

[@srini2010srini]

Geat explanation. Thanks.

[@ajinkyakale8941]

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

[@thealgorists60]

Look here for full explanation: www.thealgorists.com/Algo/GraphTheory/Tarjan/SCC

[@codewithkavit2581]

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

[@matinzare2468]

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

[@shubhamb4932]

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 kzbin.info/www/bejne/l4u7mmSro6eXgKM 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])

[@indiegypsy]

The example you took is acyclic, which is the reason it returns a single SCC. Add few cycles in your graph and you will notice. This algorithm searches for cycles and its neighbours if you look at it closely.

[@shubhamb4932]

@@indiegypsy How is the graph acyclic ? I can see atleast two cycles (0,1,2) and (5,6,7,8). Also, I'm talking about the graph at 07:16 in kzbin.info/www/bejne/l4u7mmSro6eXgKM

[@indiegypsy]

@@shubhamb4932 Sorry, I did not check the video initially... Now I understood your question clearly. What you are saying makes sense. Even I checked for the correctness of the logic at other sources and what you have mentioned seems true to me too. In fact, there is a pinned comment in the video you mentioned which also discusses the same thing.

[@developmentarchive5642]

@@indiegypsy Sorry for answering late, but modifying it to low[at] = min(low[at], ids[to]) does have some effect in a range of graph does it? Because I tried the min(low[at], low[to]) and got AC for both cases. It seems like unless it goes to very specific cases like this, whichever doesn't matter.

[@apoorvedave]

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.

[@SathishBatsy]

wouldn't back tracking happens from 1->4>3->2->1, in the last final backtracking. thus taking care of 2.

[@kacy6014]

You're wrong. The order of the traversal would be 1 -> 2 -> 3 -> 2 (backtrack to 3 and assign low[3] = 2) Then dfs from 3: 3 -> 4 -> 1 (backtrack and assign low[4] = 1, low[3] = 1) Then backtrack to 2, assign low[2] = 1, then backtrack to 1, assign low[1] = 1 The wikipedia for tarjan's algorithm doesn't use "low[node] = ids[at]" either.

[@captain-ramen]

Yeah. This line really confuses me, and I can't think of a graph where it's necessary to include this line of code. @@kacy6014

[@JamesHelps]

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.

[@forthrightgambitia1032]

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

[@TryEssay]

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?

[@EshwarNorthEast]

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

[@yogeshpasari7400]

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

[@ITwithIT]

I have the same doubt

[@rohitvarma6200]

@@ITwithIT Yes, bro it is definitely necessary, once refer to this example graph, and perform a dry run, You'll get to know. Actually, you'll have only 1 SCC in this example. media.geeksforgeeks.org/wp-content/cdn-uploads/20190702123438/TarjansAlgorithms.png

[@rohitvarma6200]

Yes, it is definitely necessary, take a look at this example graph and perform a dry run. media.geeksforgeeks.org/wp-content/cdn-uploads/20190702123438/TarjansAlgorithms.png

[@idfumg]

May someone explain it in more detail, please? I've watched the video and read the geeksforgeeks.com article and I still don't understand the logic behind it. Everyone just says "do it that way". Also, it is not so clear from the video why low[node] = ids[at]. William says that we assign for each node of the SCC the same id of the current (root of SCC) node. But we may know that it is the SCC only if we see that one of the next nodes of the current node is the root of the SCC node (we have visited it earlier). Also, this step is not covered when William tells us about the thought process in the slides. When he reaches the root of the SCC he has already updated SCC values and says "All we need to do is remove the SCC values from the stack".

[@mohitmoradiya8243]

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?

[@jensBendig]

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

[@harisridhar1668]

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.

[@w花b]

Cycle detection is simply when, while doing dfs you find a node you've already visited as a neighbor of the current node you're visiting.

[@Greatfulone]

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?

[@tarunstv796]

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!

[@Saheryk]

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

[@interstella5555]

Thanks for this video :)

[@shin-yeunlau2400]

this really helps. thx

[@birzhanamirov8715]

Can we have Johnson's elementary cycles algorithm?

[@JuneRacoon]

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

[@GauravKumar-ue7nz]

Thank you Sir

[@Squirrelschaser]

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

[@assassin0mid]

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

[@timcowley4646]

See his Bridges and Articulation points video: kzbin.info/www/bejne/l4u7mmSro6eXgKM

[@minh_tran]

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.

[@JiangXiang]

Same question here. Would appreciate it greatly if you could explain this part. Seems to relate to the back edge vs the tree edge. But I'm not sure what's the difference in the code. Many thanks!

[@elangoravi5449]

Even I'm confused about this part. Any explanations will be helpful. Thanks

[@developmentarchive5642]

@@thealgorists60 I'm sorry if my comment is late, but although it's necessary to distinct between low[at] = min(low[at], ids[to]); and low[at] = min(low[at], low[to]); in cases like bridges and articulation points, does it actually matter in this specific case of finding SCCs? Like, I've tried both method, and both return AC (accepted) on the checker server, for the SCC problem (not the bridges or articulation points, of course).

[@asifahmed1323]

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?

[@constantijndekker8343]

Wouldn’t there be 4 SSC’s in such a graph (the length of the chain)?

[@toddchaney2454]

@@constantijndekker8343 No, because you cannot get from B to A. Looks like you can only get from A to B. To be SCC you need to be able to get to every single node from every node in the SCC so like if AB that would be SCC.

[@constantijndekker8343]

Todd Chaney Hello Todd, what I meant was that {A}, {B}, {C} and {D} are distinct strongly connected components (so there are 4). I agree that A and B do not belong in the same component, because, as you write, you cannot get from B to A in any way.

[@ShawnDypxz]

what do you mean by lowest node id?

[@bonopo]

can you use tarjan to find articulation points?

[@becomingbesthackerprogramm4644]

Loved it

[@dridhta]

Cool as ever.

[@thealgorists60]

If you are still hungry to know more about Tarjan's Algorithm, and especially, if you are curious to know how Tarjan's Algorithm is derived and why this algorithm actually works, visit the below links: Full explanation: www.thealgorists.com/Algo/GraphTheory/Tarjan/ArticulationPoint Finding Bridges: www.thealgorists.com/Algo/GraphTheory/Tarjan/Bridges Finding SCCs: www.thealgorists.com/Algo/GraphTheory/Tarjan/SCC

[@shauryatomer1058]

thanks for he great content

[@PradeepSingh-tq7kg]

ORZ🔥🔥🔥🔥🔥

[@polpettelover6245]

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

[@4rne]

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.

[@codapul]

Thanks you~!

[@tuhinmukherjee8141]

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

[@rohangupta1499]

Awesome

[@tempregex8520]

why is node 4 at this location kzbin.info/www/bejne/rYbKiItmo8hnhLs 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