Good morning everyone. I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems was asking for an algorithm. The problem is:
Let $R = (G,S,T,c)$ be a network, $x$ is a flow in $R$ and $(S,T)$ a cut in $R$. Write an algorithm of complexity $\mathcal O(n+m)$ which will decide if $x$ is a maximum flow and $(S,T)$ a min cut, simultaneous.
Here I tried to use Ford Fulkerson with a queue, but I think my problem was on the queue. I didn't know how to include the min cut in the Ford Fulkerson Algorithm.
What is the right algorithm for this?