PROBLEM LINK
DIFFICULTY
Medium
PREREQUISITES
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.