phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

AGC013 B. Hamiltonish Path

問題

N頂点M辺の連結で単純な無向グラフが与えられる。
このグラフにおける以下の条件を満たすパスを1つ出力せよ。

  • 2頂点以上
  • 同じ頂点を通らない
  • パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

制約

2 <= N <= 10^5
1 <= M <= 10^5

解説

直感的に、できるだけ長いパスを作った場合、パスの端点の近傍がパスの頂点集合に含まれる可能性が高そうなことがわかる。
ある頂点vから、条件を満たす端点wを見つけるまで、パスを伸ばしていくことを考える。


伸ばしていったら端点wが見つかると仮定する。
もし近傍N(v)が1個の場合、そこを端点とすればすぐに条件を満たせるので問題ない。
もし近傍N(v)が2個以上の場合、とりあえず1つを選んで伸ばしていき、端点wを見つける。
パスを伸ばしていったとき、近傍の頂点N(v)がすべて含まれれば条件を満たす端点となり得ることがわかるし、近傍の頂点でパスに含まれない頂点がある場合は、頂点vは端点として条件を満たせない頂点とわかる。
満たしていない頂点の場合にも、パスを伸ばしていくことができるので、条件を満たす端点v'を見つけるまで伸ばしていけばよい。


端点wが見つからないことがあるかどうかが問題だが、伸ばしているパスの端点xの近傍は伸ばせば伸ばすほどすでに訪れている可能性が増えていき、最終的に「動けなくなる=すべての近傍にすでに訪れている状態」になるので、端点wは見つかる。

反省

最初、A-B-C-Dみたいなグラフがあったときに、「A-B」も「パスの少なくとも一方である端点Aと直接結ばれている頂点Bがパスに含まれている状態」なので、条件を満たすかと思ったらサンプルでWAして混乱してた。
(「パスの両方の端点A,Bの近傍N(A)とN(B)の和集合N(A)∪N(B)がパスに含まれている」ことだった)