1781. The Fewest One-Way Journeys

A DIRECTED graph has n vertices and m arcs. A JOURNEY runs arcs end to end, always forwards and never jumping: the arc after u->v must start at v. A journey may be a single arc, and it may end where it began.

Print the fewest journeys needed so that every arc is used exactly once in total.

1->2, 2->3, 3->1 -> 1 one closed journey 1->2, 2->3 -> 1 one open journey 1->2, 1->3 -> 2 nothing can follow 1->2 and then 1->3 1->2, 3->4 -> 2 two separate pieces no arcs at all -> 0

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

Problem 1777 answers the undirected version. Both rules in full, so they are not blurred together:

``` undirected per piece carrying edges: max(1, (number of odd DEGREES) / 2) directed per piece carrying arcs: max(1, total POSITIVE excess in it)

excess(v) = outdeg(v) - indeg(v) ```

No halving, and a sum of surpluses rather than a count of unbalanced vertices. Take 1->2, 1->3, 1->4. Undirected, vertex 1 has degree 3 and each leaf has degree 1, so four degrees are odd and problem 1777 answers max(1, 4 / 2) = 2. Directed, the answer is 3: no two of those arcs can follow each other at all, since all three leave vertex 1. That graph is a declared test here for exactly that reason.

## What most people try first

Counting the vertices that are out of balance. On 1->2, 1->3, 1->4 that is four vertices, and the answer is 3. On a directed triangle it is zero vertices, and the answer is 1, not 0. Both directions of error appear in the same formula, which is why the max(1, ...) and the use of the SIZE of the surplus both matter.

## The method

for each piece that carries at least one arc, ignoring directions when deciding what a piece is: P = sum of excess(v) over the vertices in it where excess(v) > 0 add max(1, P) pieces carrying no arcs add nothing

## Why it is correct

Work inside one piece.

LOWER BOUND. Fix any set of journeys covering the piece. For a vertex v, every journey that passes THROUGH v uses one arc in and one arc out, so it consumes v's in and out counts equally. The only places the counts can differ are the STARTS and ENDS: a journey starting at v consumes one extra outgoing arc, and one ending at v consumes one extra incoming arc. So the number of journeys starting at v minus the number ending at v is exactly excess(v). Summing over the vertices where the excess is positive, at least P journeys must start somewhere with a surplus, so at least P journeys exist. And a piece with at least one arc needs at least one journey, hence max(1, P).

UPPER BOUND. Add P arcs as problem 1780 does, pairing surplus incoming with surplus outgoing, and the piece becomes balanced, so problem 1774's directed condition gives one closed journey over everything. Cutting that journey at each of the P added arcs and discarding them leaves exactly P journeys covering the original arcs, so P suffice when P > 0. When P = 0 the piece is already balanced and one closed journey covers it.

## Why pieces are decided with directions IGNORED

A journey cannot leave the weakly connected piece it starts in, so journeys never span two pieces and the pieces add up independently. The stronger notion, strong connectivity, is the wrong one: 1->2, 2->3 is not strongly connected and still needs only one journey.

## The boundaries that break a careless implementation

m = 0 gives 0, not 1. There is nothing to cover.

A piece that carries no arcs, which is to say an isolated vertex, must add nothing. Looping over the piece labels and adding max(1, P) for every label counts every isolated vertex as a journey, and a graph with n = 200000 and m = 0 then prints 200000 instead of 0. This is the single most common way to get this problem wrong.

A self-loop adds one to both degrees and changes no excess, but it IS an arc, so its piece counts: n = 1, m = 1 with the loop 1->1 answers 1.

## Cost

O(n + m): the degrees in one pass over the arcs, the pieces by one iterative search over the underlying undirected graph, then one pass over the vertices. The search is iterative because a path of 200000 vertices is permitted and recursion on it overflows Python's limit of 1000 and the default stack elsewhere.

## Overflow

The answer is at most m, which is 200000. No quantity here approaches the 32-bit signed limit of 2147483647.

## Worked example

arcs: 1->2, 1->3, 1->4, 5->6 pieces: {1,2,3,4} and {5,6} excess: 1 -> +3, 2 -> -1, 3 -> -1, 4 -> -1, 5 -> +1, 6 -> -1 piece 1: P = 3 -> max(1, 3) = 3 piece 2: P = 1 -> max(1, 1) = 1 answer: 4

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - self-loops can occur, change no excess, and still count as an arc that needs covering - parallel arcs can occur and are separate arcs - the graph may be disconnected, and pieces carrying no arcs contribute nothing