ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC142 F - Pure

問題
提出コード

解法

方法は、i番目からi番目に戻ってくるサイズが最小の閉路について、問題の条件を満たしているかどうか調べる、というものです。
これを全てのiについて調べ、存在すればそれを答えればよいです。
何故なら、与えられたグラフの中で、最小のサイズの閉路を見つけると、それが問題の条件を満たすグラフになるからです。
まず、問題の条件を満たす閉路が1つあったとします。
そこに、辺を1つ追加すると、その閉路は問題の条件を満たさなくなってしまいます。
しかし、その閉路についてよく見ると、追加した辺を上手く使うことで、問題の条件を満たすような閉路が必ずどこかに存在しています。

f:id:emtubasa:20190928230144p:plain

例えば、黄色と青の辺からなる、問題の条件を満たす閉路が存在したときに、橙の辺を追加したとしても、黄色+橙の辺と、それにつながってる頂点のみを選ぶことで再び問題の条件を満たす閉路が完成します。
こうして完成した閉路に、適当な頂点と辺を追加したものが問題で入力されるグラフになるので、この一番小さい閉路を探せばよいことになります。
そして、それは上記の方法で求めることができます。
具体的には、閉路を探すパートについてはBFSとその復元(1つ前に通った頂点をメモしておく)を行い、問題の条件を満たすかどうか検査するパートでは、選んだ閉路につながっている辺についてチェックし、どこかで出次数か入次数が2以上になっている頂点が存在しないか見ればよいです。
結果的にはO(N(N+M))ぐらいで解けます。

感想

上手い実装方法がわからなかったのでこうなりましたが、バグなくかけたのでまぁ良かったです。