- run the max-flow algorithm, such as Ford-Fulkerson or Edmonds-Karp, and keep the residual graph as G`.
- run DFS, from s and t, on G` and find out a reachable set R1 and R2.
- if and only if R1 + R2 = E, then return true, otherwise, return false.
For a directed graph G(V, E). We could do the following to verify the unique or not.
- run the max-flow algorithm;
- for each edge e though the min cut, increase the capacity;
- if the max flow does not change, the min cut is not unique; otherwise, it is unique.