オイラー路の構築（有向グラフ） C#編（paizaランク A 相当）

グラフ上の任意の頂点から出発して、すべての辺を通るような一筆書きをすることができるようなグラフを準オイラーグラフと呼びます。また、そのような一筆書きの順番で頂点を並べたパスをオイラー路と呼びます。ただし、始点と終点が同じ頂点である必要はありません。

n 頂点 m 辺の有向グラフが与えられます。i 番目の辺は頂点 a_i から頂点 b_i に向かっています。なお、グラフは自己ループや多重辺を含む場合があります。

このグラフは準オイラーグラフになっています。そこで、このグラフのオイラー路を構築してください。
以下の方針や擬似コードも参考にしてください。

・ 方針
今見ている頂点から、「行き止まりになるまで進み続けて、通った頂点を戻りながらパスに追加していく」ということを辺がなくなるまで繰り返す。

・ 擬似コード
以下の関数を定義し、main 関数内で用いることで実装を完成させましょう。

// 隣接リスト g を用いて動的配列 path に頂点を追加していく関数
dfs(v, g, path):
    while g[v] が空でない:
        u = g[v] の末尾の要素
        g[v] の末尾の要素を削除
        dfs(u, g, path)
    path に v を追加

// オイラー路を構築する関数
construct_eulerian_path(g, path):
    // 出次数が入次数より 1 大きい頂点 (= 始点) を探す
    start = 0
    for v = 1 から n まで:
        if 入次数(v) + 1 == 出次数(v):
            start = v
            break

    // オイラー路を構築する
    動的配列 path を空で初期化
    dfs(start, g, path)
    path を逆順にする    // 頂点が逆順に追加されるので元に戻す
    return path