1774. The Same Question With One-Way Arcs

A DIRECTED graph has n vertices and m arcs, each arc runnable only from u to v. You want to traverse every arc exactly once in a single continuous journey, always respecting the direction. Print

CIRCUIT if that is possible AND the journey can end where it began PATH if it is possible but only by ending somewhere else NONE if it is not possible at all

A graph with no arcs is CIRCUIT.

1->2, 2->3, 3->1 -> CIRCUIT 1->2, 2->3 -> PATH 1->2, 1->3 -> NONE two arcs out of 1 and nothing returns to it 1->2, 2->1 -> CIRCUIT 1->2, 1->2 -> NONE two parallel arcs, nothing comes back to 1

## THE DIRECTED CONDITION IS NOT THE UNDIRECTED ONE WITH ARROWS DRAWN ON

Problem 1772 gives the undirected rule: all edges in one piece, and 0 or 2 vertices of odd degree. Written out separately, because blurring the two is the commonest error in this whole topic, the directed rule is:

every ARC-BEARING vertex lies in one piece of the UNDERLYING UNDIRECTED graph and, with diff(v) = outdegree(v) - indegree(v): every diff(v) == 0 -> CIRCUIT exactly one diff == +1, exactly one == -1, and every other diff == 0 -> PATH, starting at the +1 anything else -> NONE

Three differences from the undirected statement are worth naming.

Parity is irrelevant. 1->2, 1->2 has both degrees even in the undirected sense and is NONE, because vertex 1 has out 2 and in 0.

A single vertex off by two fails even when everything balances overall. The totals sum(indegree) and sum(outdegree) are both m for every digraph, so sum(diff) is always 0. That identity says nothing: it holds for 1->2, 1->2, 3->1, 4->1 as much as for a circuit. The condition is per vertex.

Connectivity is tested on the UNDERLYING undirected graph, not on directed reachability. With the degree condition satisfied, underlying connectivity already forces strong connectivity on the arc-bearing part, so testing the cheaper thing is enough and testing one-way reachability from a single vertex would wrongly reject nothing but is extra work.

A SELF-LOOP adds 1 to the indegree and 1 to the outdegree of its vertex, so its diff is unchanged, exactly as it leaves parity unchanged in the undirected case. It is the one place the two rules agree for the same reason.

## What most people try first

Checking indegree(v) == outdegree(v) for every v and nothing else. That misses the PATH case entirely, reporting NONE for 1->2, 2->3.

The second attempt adds the PATH case and forgets connectivity: 1->2, 2->1, 3->4, 4->3 has every diff zero and is NONE, two separate circuits with no way between them.

The third checks connectivity by reachability from vertex 1 along the arcs. On 2->3, 3->2 that search from vertex 1 reaches nothing and the answer is CIRCUIT, so the test has to start from an ARC-BEARING vertex and run on the underlying undirected graph.

## Why the degree condition is necessary

Every time the journey passes through v it uses one incoming arc and one outgoing arc. So indegree(v) equals outdegree(v) for every interior vertex. The start uses one extra outgoing arc and the end one extra incoming arc, so the start has diff +1 and the end -1, unless they are the same vertex, in which case the extras cancel and every diff is 0.

## Cost

O(n + m): one pass for the two degree arrays, one iterative search on the underlying undirected graph. The search must be iterative, since a directed path of 200000 vertices is permitted.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - the arcs are DIRECTED, so `u` to `v` is not usable from `v` to `u` - `u` may equal `v`, so self-loops can occur, and a self-loop adds 1 to each of the two degrees - the same ordered pair may be listed more than once, so parallel arcs can occur - the graph may be disconnected, and vertices with no arcs never prevent a journey