二重オイラー閉路

次数 $1$ の頂点では、入ってきた辺を直ちに戻る必要があるため解は存在しない。逆に、すべての頂点の次数が $2$ 以上なら解は存在する。橋があってもよい。

各辺を二重化し、Hierholzer 法でオイラー閉路を作る。同じ元の辺を連続して通る箇所を U ターンと呼ぶ。最後と最初の辺のつなぎ目も調べる。

U ターン $u\to v\to u$ を選ぶ。$v$ の次数は $2$ 以上なので、別の訪問 $x\to v\to y$ がある。辺 $uv$ の使用 $2$ 回は選んだ U ターンに含まれるため、$x\neq u$、$y\neq u$ である。$x=y$ でもよい。

二つの訪問間の区間 $v\to u\to\cdots\to x\to v$ を反転する。境界は $u\to v\to x$ と $u\to$ となり、どちらも U ターンではない。内部の U ターンの有無は変わらず、閉じた歩道であることと各辺の使用回数も保たれる。したがって U ターン数は少なくとも 減る。

初期の U ターン数は $M$ 以下である。各反転を探索込みで $O(M)$ 時間で行えば、時間計算量は $O(N+M^2)$、空間計算量は $O(N+M)$ となる。全ケースの時間は 以下である。

小課題 1 では辺の使用回数を三進数で管理し、現在の頂点、直前の辺、使用回数の状態についてメモ化探索する。最初の入力辺を一方向に通るところから始めてよい。解を回転し、必要なら反転すればこの形になる。時間は $O(NM^2 3^M)$、空間は $O(NM3^M)$ であり、、 なら十分である。

小課題 2 のグラフはパスまたはサイクルである。パスには解がなく、サイクルは同じ向きに $2$ 周すればよい。時間と空間は $O(N+M)$ である。小課題 3 では上記の反転法を用いる。

Solution written by GPT