### checkMate09's blog

By checkMate09, history, 3 years ago, ,

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__

• +5

 » 3 years ago, # |   +3 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 AcceptedCAPCITYBOTTOM427C - Checkposts
•  » » 3 years ago, # ^ |   0 Then why the tutorial of geeksforgeeks say it's wrong way and we shall use disc instwad of low
 » 3 years ago, # |   0 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.
 » 3 years ago, # |   -10 Tarzan's Algorithm works as follows. while(forest) { while(distance(vine,vine+1) > arm_length) keepSwinging(); jump(); vine++; } 
 » 14 months ago, # | ← Rev. 4 →   -11 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.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.
•  » » 12 months ago, # ^ |   +3 there is already a similar question on Stack Overflow: https://stackoverflow.com/questions/31896765/tarjans-strongly-connected-components-algorithm-why-index-in-the-back-edgethe 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
 » 12 months ago, # |   +3 Tarzan's algorithm is very simple. It jumps from vine to vine to reach his destination.
 » 12 months ago, # |   0 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.