Contest

Medium

Maximum flow

# SOLUTION

The structure of the roads given represent a directed graph without self loops and parallel edges. In a directed graph, the sum of in-degrees and out-degrees is same. If they’re not same, then it’s not possible to build a directed graph with their vertices having these in and out degrees.

If the sums of in and out degrees are same, we can get the corresponding digraph by constructing a flow network and inspecting the edges. We build a network consisting of 2*V + 2 vertices. For each vertex

``````v
``````

of the digraph, we create two vertices in the flow network,

``````Vout
``````

and

``````Vin
``````

. We create two more vertices,

``````S
``````

and

``````T
``````

, the source and sink respectively. We create an edge from

``````S
``````

to each

``````Vout
``````

and the label the edge weight as the out-degree of vertex

``````v
``````

. We also create an edge from each

``````Vin
``````

to

``````T
``````

, with edge label as in-degree of

``````v
``````

. Finally we create an edge from each

``````Vout
``````

to each

``````Vin
``````

which have a positive out-degree and in-degree respectively, and give these edges weight of 1 each.

The max flow in this network from

``````S
``````

to

``````T
``````

denotes the number of edges in the digraph, and it is equal to the sum of in-degrees/out-degrees. We can test the reverse edges to find the ones with positive flow, and thus gather information about the out-going edges from each vertex, and hence the complete digraph.

The constraints were very low, even the slowest flow implementations would have passed the time limit.