# 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.