AtCoder Beginner Contest 142: F - Pure

$N$ 頂点 $M$ 辺の有向グラフ $G$ が与えられます。
このグラフの頂点には $1$ から $N$ までの番号が付けられており、 $i$ 番目の辺は頂点 $A_{i}$ から頂点 $B_{i}$ に向けて張られています。
このグラフは自己辺や多重辺を持たないことが保証されています。

すべての頂点の入次数が $1$ 、出次数が $1$ であるような $G$ の誘導部分グラフ (注記を参照) が存在するか判定し、存在するならその一例を示してください。
ただし、空グラフは含めないものとします。

最近解いて、ちょっと面白かったのと公式の解説が個人的に若干わかりづらかったので、書き記そうと決意しました。(記念の1個目の解説記事！)

まず「すべての頂点の入次数が $1$ 、出次数が $1$ であるような $G$ の誘導部分グラフ」の「すべての頂点の入次数が $1$ 、出次数が $1$ であるような」とは何かを考えてみます。

簡単に考えると、１つの閉路のみによって構成されるグラフが条件を満たすことがわかります。

※これは閉路グラフという名前があり、n個の辺からなる閉路グラフをC_nといいます。

従って、誘導部分グラフの定義から、とある閉路に含まれる頂点を抽出したとき、元グラフのそれら頂点間に存在する辺を抽出したら閉路グラフになっていればいいです。

ただし、ここでどの閉路を抽出すればいいのか？という問題が生じます。

なので、もう少し考えてみることにして、例えば先ほどの閉路グラフに辺を追加することを考えました。

この点線のどれかに有向辺がつくことを考えてみます。

例えば、左の点線に２から５へ向かう有向辺をつけることを考えたとき、２の出次数、５の入次数が２になってしまい当然求めるグラフの条件を満たさなくなります。

しかし、ここでグラフ全体に着目すると、２→５→６→１→２へと向かう閉路が出来上がります。ここで、閉路グラフに辺を追加すると部分グラフから閉路ができるのではないか？と考えました。

例えば、５→２へと逆の方向に辺を追加することを考えると、今度は先ほどの閉路の部分グラフでは使わなかった辺を使って２→３→４→５→２と閉路が構成できることがわかります。

また、頂点数３の閉路グラフはこれ以上辺が追加できないので条件を満たすこともわかります。

したがって、閉路に対して辺を追加することでより小さい閉路を構成できるため、閉路が存在した場合閉路にどんなに辺を追加しても条件を満たす閉路を構成できる→グラフの閉路から誘導部分グラフを抽出したときかならず条件を満たすグラフがその誘導部分グラフの部分グラフに含まれる、ということになります。

実装方法は諸説ありそうですが、僕は頂点を削っていく方法ではなく、全ての頂点に対して最短で戻ってこれるようなパスを探す→そのパスが条件を満たすかどうかを調べるという方法で実装しました。

これの正当性は、条件を満たすグラフはある頂点に対して戻ってくるまでの最短経路になる(寄り道するならそもそも条件を満たさない)ということからわかります。

計算量はすべてがコスト１の辺のグラフと見て閉路検出に幅優先探索を用いてO(M), これを全ての頂点に行うので総計算量はO(N * M)になりました。

kaikey’s diary