問題
考察
問題で与えられるグラフには必ず有向閉路が1つ以上存在しています。そのどれか1つを求めてくださいという問題です。問題文から、「ある頂点」は必ず1つだけ有向の辺が伸びていることが分かります。さらに有向閉路は必ず存在することから、任意の頂点$A_i$から有向辺をたどっていくことで必ず有向閉路を周回することになります。そこで、下記のような手続きで有向閉路1つを求めることができます。
- 始点となる頂点を決め打ちする。
- 訪れた頂点を記録しながら、有向辺をたどる。
- 1度訪れた頂点を再び訪れた時点で1度たどるのを止める。
- 「3で止まった頂点」を始点として、訪れた頂点の順番を記録しながら有向辺をたどる。
- 再び「3で止まった頂点」に戻ってくる。このときに、「4で記録した頂点の順番」が求めるべき有向閉路の1つになる。これを出力する。
これなら計算量も$O(N)$には収まると思われるので、十分間に合いそうです。
上記の手続きとなるようなコードを実装していきましょう。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。