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.
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.
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.
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!
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?
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.
@@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.
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 :)
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
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
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.
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??
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
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.
@@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?
@@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
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.
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 ruclips.net/video/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])
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.
@@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 ruclips.net/video/aZXi1unBdJA/видео.html
@@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.
@@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.
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?
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 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
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.
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.
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.
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!
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?
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?
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?
@@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
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
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".
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 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.
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.
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.
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!
@@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).
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.
why is node 4 at this location ruclips.net/video/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
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_ ?
This series of algorithm explanation is really awesome and helpful!
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.
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.
Your channel deserves much more views ! Subscribed !
I'm not a native English speaker, your English is slow and clear, very nice video :), learn algorithm and your English pronunciation
Thanks!
Best video on RUclips for Tarjan's Algo
I just love the way you explain everything and make it easy to understand. Kudos to that!
incredibly well explained, you're trully talented at this, keep up the good work!
This is one of the best video on Tarjan's Algorithm . Thanks alot !!! 😄
This is a great explanation!
great visuals! beautiful algorithm
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.
Tell me if I'm wrong btw.
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.
did not Tarjan lived in the jungle.
Jen is disappointed reading this
Love your way of explaining algorithm concepts
Thank you so much for this, all your videos make these concepts so much easier and clearer to understand!
This is pretty much exactly what I needed.
Thanks for the well made explanation. :)
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!
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?
@@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.
Thanks
Great explanation. Thanks William
Just to drop this! Great
I just love your content! 🙌
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.
even i have same question do u get the info regarding this ,this hould be written or not?
@@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
@@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.
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 :)
thank you so much, watched this just in time!
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.
an excellent explanation, thanks a lot.
Great video, thank you for the explanations
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
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
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.
Clear and awesome!
Incredibly helpful.
It took some time to understand, your video helped
Very nice explanation. Thank you
That was a great explanation! Thanks!
thanks for a super clear example
Very comprehensive!
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??
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
why did you remove your bridges and articulation points video ? you kept the older version of this. awesome series though !
Keep on making helping a lot, you are bringing change!!! thanks man
Beautifully Explained :)
my teacher took 1.5 h to explain this concept and explained it in 9 min ( after playing it at 2x speed😉). Thank you
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
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)?
Good question, i also didn't get it
Same question!
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.
@@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?
@@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
Can you make a video on the theme of the Feedback arc set? Your videos are very good!
Wouldn't 16:19 be cleaner with a while loop?
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
very beneficial , Thank You
Thank you very much, that was amazing!
Amazing explanation! Thanks!
This was a beautifully written explanation. Thank you!
Awesome dedication to helping the viewer understand rather than "look what a l33t h4x0r i am"
Thts a indepth Easy Explanation of a Complex Algorithm ,
You are the goat brother! 🐐
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.
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 ruclips.net/video/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])
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.
@@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 ruclips.net/video/aZXi1unBdJA/видео.html
@@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.
@@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.
amazing videos man!
Awesome! Thank you!
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?
Super Good Explanation!
Thank you very much!!
Geat explanation. Thanks.
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
Yeah, it seems to work without the low[node] = ids[at], at least when I ran it with the example from the video.
@@MatthewLuigamma032 It doesn't work for all examples tho
@@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
Very interesting video to learn from, thanks
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?
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.
wouldn't back tracking happens from 1->4>3->2->1, in the last final backtracking. thus taking care of 2.
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.
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
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.
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.
Very nice video, which editing software did you use to make the video William ?
Do I understand correctly that you explained to us that the effect of algorithm finding value of index is highly dependent on... indexing?
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!
I don't understand what will be the run time and space complexity?
this really helps. thx
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?
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?
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?
hi, why does the algo ensure low[node] after popping from stack? does this line low[at] = id++ not guarantee that?
Look here for full explanation: www.thealgorists.com/Algo/GraphTheory/Tarjan/SCC
Is the low[nodes] = ids[at] necessary?
I have the same doubt
@@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
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
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".
Thanks for this video :)
Anyone knows of any problems on LC that relies on finding SCCs?
1319 is connected components, but can't find a question for SCC.
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?
Wouldn’t there be 4 SSC’s in such a graph (the length of the chain)?
@@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.
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.
Can we have Johnson's elementary cycles algorithm?
Thank you Sir
whats if node 0 was not visited when we reached 5?
can you use tarjan to find articulation points?
Loved it
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.
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!
Even I'm confused about this part. Any explanations will be helpful. Thanks
@@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).
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.
Good explanation. How do you extrapolate this to finding critical connections in a graph ?
See his Bridges and Articulation points video: ruclips.net/video/aZXi1unBdJA/видео.html
thanks for he great content
Good Idea, to separate the Lowlink-calculation from the Rest!
Hey, are you active on some media. Would love to talk!
Cool as ever.
ORZ🔥🔥🔥🔥🔥
why is node 4 at this location ruclips.net/video/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
Thanks you~!
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_ ?
Awesome