Mail Delivery - Algorithm

Algorithm: $1.$ Check if all vertices have even degree

$2.$ Check if graph is connected (DFS from vertex $1$)

$3.$ If checks pass, run Hierholzer starting from vertex $1$

$4.$ Output the resulting path

Implementation detail: For undirected graphs, each edge appears twice in the adjacency list. When you use one direction, mark both as used.

A common approach: store edge indices and mark edges by index rather than by endpoint pairs.

This runs in $O(E)$ time and uses $O(E)$ space.