Codeforces #150 Div1B/Div2D Hydra

問題要約：

頂点u-vをつなぐ辺を一つ持ち、端点の片方がuの辺をh個、端点の片方がvの辺をt個持つグラフをHydraグラフと呼ぶ。(図参照)　頂点数n,mのグラフGと整数h,tが与えられるとき、Gの部分グラフにHydraグラフが含まれるか？

制約：

\(n,m\le 10^5\)

\(h,t\le 100\)(超重要)

解法：

Hydraグラフのu-vをつなぐ辺を全通り試そう。u-vを固定すると、注目する頂点は以下の3つに分類できる。

①uと隣接している頂点

②vと隣接している頂点

③u,v両方と隣接している頂点

図にすると、このように分類できる。

（ただし、③に含まれるものは①、②から除外する）

頂点xの次数を\(deg(x)\)で表す。この時、①②③の個数をそれぞれ\(P,Q,R\)とすると、

\(P+Q+R=deg(u)+deg(v)\)である。

また、Hydraグラフを作ることができる必要十分条件は

\(P+p\le h,Q+q\le t,p+q\le R\) である。

P,Q,Rを求めることは簡単ではなさそうだ。ここでは前処理により簡単に求められる\(deg(u)\)と\(deg(v)\)からHydraグラフの有無を検出しよう。

A.\(deg(u)\lt h+1\)または\(deg(v)\lt t+1\)の時、

そもそも辺が足りない。当然ながらHydraグラフは作れない。

B.\(deg(u)\le h+t+1\)かつ\(deg(v)\le h+t+1\)の時、

たとえ全ての頂点が③であっても、また逆に③の頂点が一つもない場合でも、Hydraグラフを構築できる。

C.その他

この場合は素直に\(P,Q,R\)を求めよう。ここで\(h,t\le 100\)と小さいことを活用できる。

AでもBでもないので、\(h+1\le deg(u)\lt h+t+1\)かつ\(t+1\le deg(v)\lt h+t+1\)である。つまり、頂点u,vに隣接する頂点を全列挙しても\(deg(u)+deg(v)=\)高々\(2(h+t+1)\)個であり、計算量は全体で見ても\(O(m(h+t))\)と十分小さい。

以上のA,B,Cの場合分けは以下のように図示できる。

h,tの制約を見落としていてvirtual中は解けなかった。