Hello Codeforces,

I've asked a question related to Tarjan's algorithm of finding SCC at Quora since a while with a lot of people want the answer as well as i sake can any one help us ?

https://www.quora.com/How-does-Tarjans-SCC-algorithm-work?__snid3__=356797187&__nsrc__=2&__filter__

I always find this question very interesting. I am almost convinced that both ways will lead to the same results (finding the strongly connected components correctly).

Since

`low[u]`

stores the minimum discovery time of a node reachable from u, for all neighbors v of u already visitedin the same SCC,`low[v] <= low[u] and disc[v] <= low[u]`

I solved these problems using

`low[u] = min(low[u], low[v])`

and`low[u] = min(low[u], disc[v])`

and both ways got AcceptedCAPCITY

BOTTOM

427C - Checkposts

Then why the tutorial of geeksforgeeks say it's wrong way and we shall use disc instwad of low

Competitive Programming has

in their implementation of Tarjan's SCC but used

for the Articulation/Bridge finding version Tarjan's. Can't seem to find any good answers for this.

Tarzan's Algorithm works as follows.

For articulation point when you encounter a visited vertex use : low[u]=min(low[u],disc[v]).

You may use the above line even for bridges and SCC, this is what most people do and their code looks pretty similar in all three problems.

But when you are looking for bridges/SCC you may use low[u]=min(low[u],low[v]) with a condition that v is not the parent u (the condition is only for bridges, for SCC its a directed graph anyway).

Try to analyse test cases with cycles in all three problems (specifically when the root is not a part of the cycle), and you will be able to see where what goes wrong if you use low[u]=min(low[u],low[v]) in all three problems.

It took me a while to properly dry run my code and figure out what works when and why with complete proof of correctness.

The final conclusion I came to is : low[u]=min(low[u],disc[v]) is necessary for articulation point for the other two cases you can use low[u]=min(low[u],disc[v]) or low[u]=min(low[u],low[v]), either way the algorithm would be correct.

So be patient.

PS: I see lots of negative reactions from people who seem to have just read tutorials and learnt the algorithm in a specific way. All I am saying is low[u]=min(low[u],low[v]) works in case of SCC, bridges, the standard way is also not wrong. The difference is based on how you define low to begin with. Please respond with a reply and preferably a test case showing why you believe the point I have raised has problems. Merely down voting without reasoning helps nobody.

there is already a similar question on Stack Overflow: https://stackoverflow.com/questions/31896765/tarjans-strongly-connected-components-algorithm-why-index-in-the-back-edge

the point is, if you're writing low[u] = min(low[u], low[v]) for some node v in the stack, then your low[u] is not well-defined (since low[v] is only defined

afterit exits the stack)rather than "the furthest up you can travel back with one reverse edge", your low[u] would be "somewhere further up the furthest up you can travel back with one reverse edge", and would look silly on a scientific paper... which is probably why Tarjan chose the other way of implementation in his original algorithm.

yes, your code works for finding bridges and SCCs. tbh, I write code like that for SCCs as well =) have a nice day

Tarzan's algorithm is very simple. It jumps from vine to vine to reach his destination.

I think the difference only matters for articulation point/bridges Tarjans because of definition: it must disconnect the graph after removing one edge/vertex. A simple case like the following will fail with low = min(low, low) implementation because it does not differentiation between one or multiple removals, while min(low, disc) does.