I didn't say that it was the residual graph. It is the original one. I think that there is only one thing that is vague: i didn't mention edge capacities. This was kind of intentional to not complicate the draw. For me the lack of this info, would point that capacities were equal (that was my intention).

edge 2 edge 1 Source <------- A <------- Sink

In this case both "edge 2" and "edge 1" are possible answers, but "edge 1" has minimum index.

"Well, do we need it? :) I mean, is there any more or less practical problem that asks it?"

A problem from usaco training discussed here. I didn't understand well why the trick works. And the reference solution (used that method: dfs from the source) was changed because it is wrong.]]>

Did you even read my post ? :)

Yes.

It doesn't work if we want the minimum set of edges with smallest index.

Well, do we need it? :) I mean, is there any more or less practical problem that asks it?

Here is a tough case: Source and Sink are both connected to a complete graph K_n, all egdes have the same capacity.

Consider any decomposition of the vertices of K_n into sets of != 2 vertices. Take any set S with |S| >= 3 and form a cycle with its vertices. In the 'obvious' minimum cut there are only edges (Source, v) and (v, Sink) but it is clear that with such cycle formed you can take any(but only one at a time) vertice v from it and change the edge (Source, v) to (v, next[v]). This minimum cut will contain the same number of edges and you can play this trick with any vertice in any set of any decomposition. The number of such 'min cuts' can be calculated, but even now we can say it's large enough.]]>

I said that that method answers edge number 2 because in the residual network there isn't flow from the source to A. So the 2 sets are "Source" and "A,Sink".]]>

Example:

edge 2 edge 1 Source -------> A -------> Sink

Using that method we would get edge 2, but the answer is edge 1.

Anyone know how to solve this ?]]>

You explained well how to find a minimum edges minimum cut, but we actually find only the value of the minimum cut and the number of edges it has. How do we actually find which edges exactly would make such a cut from the residual network?]]>