I know the answer to the question, but I still can't understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the residual network, and from t in the residual net work (after changing each (u,v) to (v,u)). What I can't understand: why would I get different results? Every example I am trying shows me the same: Any vertex reachable from s (not include s) is a vertex that is reachable from t. Am I wrong? and if I'm wrong, what is the reason some other case can happen?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.