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

Tarzan's Algorithm works as follows.

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

    jump();
    vine++;
}

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.

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.