D. Tanya and Password ～オイラー(閉)路～

• Quiz
  • https://codeforces.com/contest/508/problem/D
• AC
  • https://codeforces.com/contest/508/submission/64427177
• 上記提出に、オイラー路を求める構造体、あります
  • オイラー路：全ての「辺」を1度ずつ通る路 (Trail)
  • 参考：全ての「点」ならハミルトン路 (Path)

参考（オイラー路を求める Fleury’s Algorithm）

• http://iampandiyan.blogspot.com/2013/10/c-program-to-find-euler-path-or-euler.html
• 魚拓 https://megalodon.jp/2019-1107-0409-42/iampandiyan.blogspot.com/2013/10/c-program-to-find-euler-path-or-euler.html
• (オイラーパスという呼び名は間違っているはず。正しくはオイラーTrail)

用語の注意点

• オイラーパスとは言わない（パスは頂点に注目した用語なので）
• 言うなら、Euler Trail/Circuit

コーナーケース

• 入次数、出次数だけチェックして「オイラー路, 作れる！」と判定してはいけない。連結が必要
• 下記のような場合

// 今回のデータ形式に合わせると、

4
aba
bab
cdc
dcd

• 私はbfsで連結判定した。この連結判定の開始位置も適当に0にしたりしてはいけない
• オイラー路の開始点を使った

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～