double eulerian circuit

Existence

A vertex of degree $1$ forces an immediate traversal back along the same edge, so no solution exists. Conversely, minimum degree at least $2$ is sufficient. Bridges do not prevent a solution.

Construction

Duplicate every edge and find an Euler circuit with Hierholzer's algorithm. Each original edge is now traversed twice. Call two consecutive uses of the same original edge a U-turn, including the junction between the last and first edges.

Choose a U-turn $u\to v\to u$. Since $v$ has degree at least $2$, the circuit has another visit $x\to v\to y$. Both uses of edge $uv$ are already in the chosen U-turn, so $x\neq u$ and $y\neq u$. It is possible that $x=y$.

Reverse the segment $v\to u\to\cdots\to x\to v$ between the two visits. The two junctions become $u\to v\to x$ and $$, neither of which is a U-turn. Inside the reversed segment, only the direction changes, so U-turn status is unchanged. The walk remains closed and every edge keeps its traversal count. Thus at least one U-turn disappears and none is created.

Initially there are at most $M$ U-turns, since each one uses both copies of a different original edge. Finding a U-turn, finding another visit, and reversing the segment each take $O(M)$ time. Total time is $O(N+M^2)$ and space is $$. Across test cases, time is at most . Connectivity gives .

Subtasks

For subtask 1, use a ternary mask to store each edge's usage count in $\{0,1,2\}$. Fix the first input edge as the first traversal in one direction. Any valid circuit can be rotated and, if needed, reversed to satisfy this choice. Memoize failed states consisting of the current vertex, previous edge, and ternary mask. Time is $O(NM^2 3^M)$ and space is . The bounds and make this feasible.

For subtask 2, a connected graph of maximum degree at most $2$ is a path or a cycle. A path is impossible; traverse a cycle twice in the same direction. Time and space are $O(N+M)$.

Subtask 3 uses the U-turn removal algorithm above.

Solution written by GPT