Standard disclaimer: use the algorithms from class, such as DFS, Explore, BFS, Dijkstras (using min-heaps), connected components, etc., as a blackbox subroutine for your algorithm. If you attempt to modify one of these algorithms you will not receive full credit, even if it is correct. Make sure to explain your algorithm in words, no pseudocode. Faster and correct is worth more credit.

For a flow network G = (V,E) with specified s, t V and capacities c_e > 0 for e E, you are given a flow f (you are given f_e for every e E). Note: For both parts, faster and correct. Youre algorithm should not take the same time as computing a max-flow from scratch.

Part (a): Explain an algorithm to verify/check whether or not f is a valid flow. Be sure to state and explain the running time of your algorithm.

Part (b): It is claimed that f is a maximum flow. Explain an algorithm to verify/check whether or not f is a maximum flow. Be sure to state and explain the running time of your algorithm.