ABC 399 C Make it Forest
AtCoder Beginner Contest 399 の C 問題 Make it Forest を毎日 1 時間以上かけて、やっと正解できました。
解決方法
C - Make it Forestは、グラフの問題で、森にするために切断する経路の数を答える問題でした。
例えば単純な次のようなループの場合は、それぞれ 1 ヶ所切ればループがなくなります。
そこで、最初はこのループになっている数が答えになると考えてプログラムを作成しました。
しかし 4 面体を考えると、この考えが間違いであることが分かります。
4 面体には、ループが 4 つあります。しかし、3 ヶ所の path を切れば、ループを解消できます。
そこで、通過した node に visited のマークを付けながら単純に path をたどって、次の node が visited ならばループになっている＝この path を切断する必要があるとして全ての経路をたどることにして正解できました。
RE (Runntime Error)
最初の内は、コードを提出してもほとんどのテストケースが RE (Runtime Error)になってしまいました。Runtime Error なので、文法的な間違いだと考えて見直しても間違いを見つけられませんでした。
そこで、全ての例外を catch して適当な答えを返すように修正しても RE のままでした。
そこで、文法的な問題でない可能に気が付きました。経路の探索に再帰を使ってので、メモリー制限のエラーです。そこで再帰数を制限したところ、RE から WA (Wrong Answer)となりました。やはりメモリー制限のエラーです。
メモリー制限のエラーの回避のために通過した node を stack に積んでいき、末端の node（切断して末端になった node を含む）なら 1 つ戻るを繰り返して全ての node を回るように修正しました。