sarthak1729's blog

By sarthak1729, history, 6 weeks ago, In English

I am confused about a thing we do while finding bridges

if (visited[to]) {
      low[v] = min(low[v], tin[to]);
 }

We use the above code when we find back edge to update its low but why can't we use

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

Complete Code

There is a logic for this in case of articulation points as discussed in FAQ section of this article https://codeforces.com/blog/entry/71146

But I was unable to find some counter-example for bridge? The same question was asked in the comments of article (https://codeforces.com/blog/entry/71146?#comment-598570) but I don't find the answer up to the mark.

Can you confirm whether we can use it or not and if we cant then can you provide a counter example

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it