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

Revision en2, by brdy, 2018-01-30 21:17:50


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

First,find a way from s to t.

If there is no such way,the answer is 0.

If there is such way,try to stop every edge on it and try to find bridges and upuate the answer.

How to find a bridge?

DFS it with root s,record the depth of every vertex and the least depth it can reach without passing its father.

If the least depth x can reach without passing x's father > the depth of y then (x,y) is a bridge.

Try to stop edges o(n),and finding bridges o(m).

It's o(nm).

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.

Tags bridges, graphs, tarjan


  Rev. Lang. By When Δ Comment
en2 English brdy 2018-01-30 21:17:50 347
en1 English brdy 2018-01-30 05:12:36 1170 Initial revision (published)