すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ」というのは要するに輪っかのことで、しかも輪っかを横切るショートカット辺が存在しないもののこと。N の２乗が通る制約ではあるけども、すべての頂点を始点にして輪っかを検出して、輪っかのパスを辿ってショートカット辺が存在しないことを確かめて許されるのかどうか。■提出 #43905266 (AC / 967 Byte / 77 ms)。再帰関数のパラメータとしてパスを表す配列と、再訪確認のためにパスをメンバとするハッシュ表と、調べたけどダメだったことをメモするハッシュ表を渡している。もっとうまいやりようがありそうなものだ。■輪っかの検出ロジックは、終点を決めて、終点の隣接頂点の１つを始点にして終点への到達可否を調べる。そのときに始点や中継点において、終点に到達したパスの中に２つ以上の隣接頂点(←始点や中継点にとっての)が含まれていないことを確認している。２つ以上の隣接頂点が関わる輪っかはショートカット辺がある輪っかなので。これを愚直に繰り返すと TLE になったので、ダメだった結果をメモしている。輪っかにならなかったケースとショートカット辺があったケース。メモの利用は中途半端で、輪っかの終点を切り替えるごとにリセットしてしまっている。輪っかなんだから(輪っかを検出するための便宜上の)終点をどこに取ったとしてもショートカット辺があるせいでダメだったという結果は共有できるはずなんだけどしていない。あと必要だったのは終点を含まないところで輪っかができてしまうケースの除外。それはいま関心がある部分ではないので後の処理を待ってほしい。再帰関数で同一頂点への再入を検知してリターンしないとスタックを使い尽くしてしまった。■これって強連結成分を定型的に列挙してショートカット辺をちょちょいと調べて終わりだったりしたのでは？ 自分は何か輪っかの検出で苦労して、輪っかの検出とショートカット辺の確認を同時にやろうとしてさらに苦しくなっている雰囲気。DFS ２回の SCC 分解がそらで書けるほど身についてないから仕方ないんだけど。■日記を書くために自分の解法を書いていたらこれがなんで AC なのかわからなくなってきた。それでひとつの発見があった。最初に「要するに輪っかのことで、しかも輪っかを横切るショートカット辺が存在しないもののこと」と書いたけど、ショートカット辺はただのショートカット辺ではなくて長さ１のショートカット辺だった。誘導部分グラフに含まれる辺と含まれない辺を考えれば当然のことだけど。そうするとひとつの疑問がわいて、どんなループでも、許されない長さ１のショートカット辺を本式の、ループを構成する辺として採用することで答えにすることができるのかどうか。できそうな気がする。それで実装が簡単になるかと思って別解を書き始めたけど、べつにそんなことはなかった。■提出 #43935918 (AC / 1048 Byte / 69 ms)。長くはなったけどややこしさは減って、シンプルに閉路検出＆コンパクト化で答えが得られるようになった。■この問題を選んだきっかけはこの前の ABC311-C「Find it!」で閉路検出を書いたからで(#43848448)、その目論見が外れてやけにややこしい解法に当初はなったけど、別解ができてみると狙いが外れていなかったことがわかる。グラフの形がちょっと複雑になって、閉路のコンパクト化という処理を追加したものがこの Pure という問題だった。