Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Finding bridges with an added condition in O(V+E)

Правка en2, от brdy, 2018-01-30 21:17:50

Hello,

I have recently been doing this problem 701F - Break Up.

While it does not have an explanation in the official editorial, some user made an informal editorial.

The solution goes like this

I wrote Tarjan's for finding bridges, but then realized such a solution doesn't even pass the samples because a bridge is only guaranteed to split the graph into two components, but not necessarily separating the vertex s from t. How can I modify the algorithm to only consider bridges that split s and t?

UPD: Ok. The solution I tried was to dfs rooted at s, and for each dfs call update where t is reachable from the current vertex. It gets WA on 98. Is the thought process behind this correct? (Or is different solution intended) I want to make sure I'm not looking for nonexistent bug.

Теги bridges, graphs, tarjan

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский brdy 2018-01-30 21:17:50 347
en1 Английский brdy 2018-01-30 05:12:36 1170 Initial revision (published)