Hello,↵
↵
I have recently been doing this problem [problem:701F].↵
↵
While it does not have an explanation in the [official editorial](http://mirror.codeforces.com/blog/entry/46283), some user made an [informal editorial](http://mirror.codeforces.com/blog/entry/46248).↵
↵
<spoiler summary="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).↵
↵
</spoiler>↵
↵
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](http://mirror.codeforces.com/contest/701/submission/34717590) 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. ↵
↵
I have recently been doing this problem [problem:701F].↵
↵
While it does not have an explanation in the [official editorial](http://mirror.codeforces.com/blog/entry/46283), some user made an [informal editorial](http://mirror.codeforces.com/blog/entry/46248).↵
↵
<spoiler summary="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).↵
↵
</spoiler>↵
↵
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](http://mirror.codeforces.com/contest/701/submission/34717590) 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. ↵
