Here's a couple of tips:
- Suppose you found a path with nonzero flow (i.e
>= 1
), and contained this edge e_i. How might you use this path to make the overall flow valid again? Now, suppose you aren't given this path. How might you get it yourself? - Now, you know that the max flow of the new graph is either the same, or one less than before (why?). How might you find out which in linear time?