A doubt about finding bridges in graphs

Revision en1, by sarthak1729, 2022-07-06 10:23:40

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

Tags graphs, bridges, articulation point

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sarthak1729 2022-07-06 10:23:40 1675 Initial revision (published)