e4-e5_Nf3-Nc6-Bc4-Bc5_'s blog

By e4-e5_Nf3-Nc6-Bc4-Bc5_, history, 2 years ago, In English,

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__

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 visited in 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 Accepted

CAPCITY

BOTTOM

427C - Checkposts

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Competitive Programming has

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

in their implementation of Tarjan's SCC but used

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

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

»
22 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Tarzan's Algorithm works as follows.

while(forest)
{
    while(distance(vine,vine+1) > arm_length)
        keepSwinging();

    jump();
    vine++;
}
»
3 months ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 after it 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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.