https://atcoder.jp/contests/abc142/tasks/abc142_f
$N$頂点$M$辺の有向グラフが与えられる。このグラフからノードの部分集合をとり、選んだ部分集合に含まれるノードをつなぐエッジのみで構成されたグラフ(誘導部分グラフ)のなかで、すべての頂点の入次数と出次数が1であるようなものをひとつ構築せよ。
要するに、部分誘導グラフのなかでコードレスサイクルになっているものを見つければよい。サイクルのなかに不要な辺があるとき、その辺を使ってより小さいサイクルを必ず作ることができる。このことから、グラフのなかで最小のサイクルはかならずコードレスサイクルになっていることがわかる。
最小のサイクルを見つけるには、全ノード間の距離を求めたあとで、エッジ($y\rightarrow x$)をもつようなノードのペア($x, y$)のなかで、$x$から$y$への距離が最小のものを探せばよい。見つけたら、経路復元して出力する。辺の数が少ないのでBFSが充分高速に回る。ダイクストラも間に合うらしい(未確認)
これ気づかないの悔しすぎるな。