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.
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
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!
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.
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 :)
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?
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
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?
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.
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.
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.
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.
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
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?
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
@@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".
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.
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.
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.
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).
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_ ?
As some people pointed out, the algorithm is flawed, as you present it. When you are presenting on the 8-noded graph... if there was an edge from 5 to 3, your algorithm breaks.
I just reached the enlightenment... your explanation through low-links actually confused me greatly. In the algorithm, you actually do NOT ensure that the lowlinks match, but you keep track of the lowlinks only to know when to terminate and start popping from the stack. Maybe it is just me, but I thought someone might get confused the same way.
This series of algorithm explanation is really awesome and helpful!
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.
Images speak more than the words. How Beautifully you explain such a compelling algo. Thank you!!.
By far the most succinct explanation of Tarjan's SCC algorithm, thanks!
I'm not a native English speaker, your English is slow and clear, very nice video :), learn algorithm and your English pronunciation
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.
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.
I just love the way you explain everything and make it easy to understand. Kudos to that!
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.
did not Tarjan lived in the jungle.
Jen is disappointed reading this
Your channel deserves much more views ! Subscribed !
This is one of the best video on Tarjan's Algorithm . Thanks alot !!! 😄
Love your way of explaining algorithm concepts
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
incredibly well explained, you're trully talented at this, keep up the good work!
Best video on RUclips for Tarjan's Algo
This is pretty much exactly what I needed.
Thanks for the well made explanation. :)
Thank you so much for this, all your videos make these concepts so much easier and clearer to understand!
Just to drop this! Great
This is a great 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!
great visuals! beautiful algorithm
Great explanation. Thanks William
thank you so much, watched this just in time!
my teacher took 1.5 h to explain this concept and explained it in 9 min ( after playing it at 2x speed😉). Thank you
Clear and awesome!
why did you remove your bridges and articulation points video ? you kept the older version of this. awesome series though !
Thts a indepth Easy Explanation of a Complex Algorithm ,
It took some time to understand, your video helped
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 video, thank you for the explanations
an excellent explanation, thanks a lot.
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
Very nice explanation. Thank you
Incredibly helpful.
thanks for a super clear example
Can you make a video on the theme of the Feedback arc set? Your videos are very good!
I just love your content! 🙌
Very comprehensive!
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
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.
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 :)
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?
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
Hey William! Great graph collection there, can you put videos on articulation points and bridges?
Good Idea, to separate the Lowlink-calculation from the Rest!
Keep on making helping a lot, you are bringing change!!! thanks man
Beautifully Explained :)
Thank you very much, that was amazing!
Hey William did u take down your articulation point video? I couldn't find it on your playlist
That was a great explanation! Thanks!
Very nice video, which editing software did you use to make the video William ?
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?
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.
Very interesting video to learn from, thanks
very beneficial , Thank You
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.
amazing videos man!
Amazing explanation! Thanks!
You are the goat brother! 🐐
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?
Awesome! Thank you!
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
Do I understand correctly that you explained to us that the effect of algorithm finding value of index is highly dependent on... indexing?
Super Good Explanation!
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
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!
Why we need stack data structure ? bool onStack[n] should just help ??? Please help me understand...
Wouldn't 16:19 be cleaner with a while loop?
I don't understand what will be the run time and space complexity?
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?
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
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
Thank you Sir
this really helps. thx
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".
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.
Can we have Johnson's elementary cycles algorithm?
Loved it
Anyone knows of any problems on LC that relies on finding SCCs?
1319 is connected components, but can't find a question for SCC.
Thanks!
Thanks for this video :)
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
what do you mean by lowest node id?
can you use tarjan to find articulation points?
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.
whats if node 0 was not visited when we reached 5?
thanks for he great content
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.
Cool as ever.
Hey, are you active on some media. Would love to talk!
Thanks
Awesome
Thanks you~!
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).
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_ ?
As some people pointed out, the algorithm is flawed, as you present it. When you are presenting on the 8-noded graph... if there was an edge from 5 to 3, your algorithm breaks.
I just reached the enlightenment... your explanation through low-links actually confused me greatly. In the algorithm, you actually do NOT ensure that the lowlinks match, but you keep track of the lowlinks only to know when to terminate and start popping from the stack. Maybe it is just me, but I thought someone might get confused the same way.
*scratches head* What is this sorcery?