1
A doubt about finding bridges in graphs
source link: http://codeforces.com/blog/entry/104565
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK