1780. The Fewest Arcs To Add

A DIRECTED graph has n vertices and m arcs, each runnable only from u to v. All the arcs lie in one connected piece when directions are ignored.

Print the fewest new arcs that have to be added so that some closed journey uses every arc exactly once, always respecting direction and never jumping. New arcs may join any two vertices, in either direction, and a vertex may receive several new arcs.

1->2, 2->3, 3->1 -> 0 already closed 1->2, 2->3 -> 1 add 3->1 1->2, 1->3 -> 2 add 2->1 and 3->1 1->2, 1->2 -> 1 add 2->1, used once each way round 1->2, 2->1, 1->2, 2->1 -> 0 two arcs each way, already closed

## This is NOT problem 1778's formula with arrows drawn on

Problem 1778 answers the undirected version: count the vertices of odd degree and halve it, because a new edge fixes two vertices at once. Written out in full, so the two are not blurred together:

undirected answer = (number of vertices of odd DEGREE) / 2 directed answer = total of the POSITIVE values of outdeg(v) - indeg(v)

There is no halving in the directed case, and the reason is that an arc has a tail and a head doing opposite jobs. A new arc x->y raises x's outdegree and y's indegree, so it moves x further out of balance in the positive direction unless x was short of outgoing arcs. It helps exactly one vertex that had a surplus of outgoing arcs.

On 1->2, 1->3 every vertex has even degree, so problem 1778 answers 0 for the same picture, while the directed answer is 2. That input is a declared test here for exactly that reason.

## The method

excess(v) = outdeg(v) - indeg(v) answer = sum of excess(v) over the vertices where it is positive

A self-loop adds one to the outdegree and one to the indegree, so it changes no excess at all. That is the directed echo of a self-loop adding two to an undirected degree and so changing no parity.

## Why it is correct

A closed journey over every arc exists exactly when every vertex has indeg = outdeg and the arcs sit in one weakly connected piece, which is problem 1774's directed condition. The piece is promised, so only the balance has to be bought.

LOWER BOUND. Write P for the total positive excess. One new arc x->y changes excess(x) by +1 and excess(y) by -1. The first can only make P bigger or leave it alone, and the second can only lower P by one at most. So P falls by at most one per arc, and P arcs are needed.

UPPER BOUND. The excesses sum to zero, because every arc contributes +1 somewhere and -1 somewhere. So writing out each vertex with positive excess e times, and each vertex with negative excess -e times, gives two lists of the SAME length P. Pair them off position by position and add an arc from each negative-side entry to each positive-side entry. Every excess becomes zero, and every new arc joins two vertices that already carried arcs, so the single piece stays single. P arcs are enough.

## The boundary that breaks a careless implementation

m = 0. There are no arcs, so the empty journey already uses every arc, and the answer is 0. A formula that starts by picking a vertex to journey from reads past the end of an empty list.

A vertex with no arcs at all is not a problem: its excess is 0, it contributes nothing, and it is not part of the piece the promise talks about.

## Cost

O(n + m): one pass over the arcs for the two degree arrays, one pass over the vertices for the sum. No search is needed, because connectivity is promised.

## Overflow

The sum is at most m, which is 200000, so a 32-bit integer is far from troubled. 2 * 10^9 would still fit in a signed 32-bit integer, since INT_MAX is 2147483647, and nothing here comes within four orders of magnitude of it.

## Worked example

arcs: 1->2, 1->3, 3->1 out: 1 -> 2, 3 -> 1 in: 2 -> 1, 3 -> 1, 1 -> 1 excess: 1 -> 2 - 1 = +1, 2 -> 0 - 1 = -1, 3 -> 1 - 1 = 0 positive: just vertex 1, with +1 answer: 1 (add 2->1)

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - self-loops can occur and add one to both degrees of their vertex, so they never change an excess - parallel arcs can occur, and two arcs the same way round are two separate arcs - all the arcs lie in one connected piece when directions are ignored, so only the balance has to be bought - vertices with no arcs may exist and are not part of that piece