I have recently been doing this problem 701F - Break Up.
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).
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.