Suppose youre looking at a flow network G with source s and sink t, and you want to be able to express something like the following intuitive notion: Some nodes are clearly on the "source side" of the main bottlenecks; some nodes are clearly on the "sink side" of the main bottlenecks; and some nodes are in the middle. However, G can have many minimum cuts, so we have to be careful in how we try making this idea precise.

Heres one way to divide the nodes of G into three categories of this sort:

We say a node v is upstream if, for all minimum s-t cuts (A, B), we have v is an element of A -- that is, v lies on the source side of every minimum cut.

We say a node v is downstream if, for all minimum s-t cuts (A, B), we have v is an element of B -- that is, v lies on the sink side of every minimum cut.

We say a node v is central if it is neither upstream nor downstream; there is at least one minimum s-t cut (A, B) for which v is an element of A, and at least one minimum s-t cut (A, B) for which v is an element of B.

Give an algorithm that takes a flow network G and classifies each of its nodes as being upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow.