I read an article about Tarjan's algorithm, blog. In this article, the author asks a question:
In case two, can we take low[v] instead of disc[v] ?? . Answer is NO. If you can think why answer is NO, you probably understood the Low and Disc concept.
I don't know why. When I am reading the similar article in wiki, I found that the code can be like that:
else if (w.onStack) then
// Successor w is in stack S and hence in the current SCC
v.lowlink := min(v.lowlink, w.lowlink)
I wanna know why the author say the answer is NO. Thanks for answering my question. Have a good day.
min(low, disc)
in his original paper), but to me either way is fine. It certainly does matter when you search for bridges and/or articulation points - in such a case usinglow
would imply that you can jump in the backward direction multiple times (not using only a single edge) and thus skip articulation points. However, In the case of finding sccs, all you need is to know if you can go to some earlier vertex within the same scc, and so, you makelow[v] <> disc[v]
, and that's what matters. – Winnickmin(low, disc)
is closer to the actual definition of whatlow
function is which in turn is present also in the aforementioned algorithms, thus I guess that's the reason whydisc
is here. – Winnick