問題概要
$N$ 頂点 $ M $ 辺の単純連結グラフが与えられるので、以下の問題のうちどちらかを解け。
1. ちょうど $\left \lceil \sqrt{n} \right \rceil$ 頂点の独立集合を見つけよ。
2. 長さ $\left \lceil \sqrt{n} \right \rceil$ 以上の単純サイクルを見つけよ。
以上のうちどちらかは必ず解けることが示せる。
$5 \le N \le 10^5$
$N-1 \le M \le 2 \times 10^5$
「 $\left \lceil \sqrt{n} \right \rceil$ 頂点の独立集合」方向から攻めていこう。これを見つけるためにはグラフの頂点が $\left \lfloor \sqrt{n} \right \rfloor$ 彩色できればよいことが分かる (この色数で彩色すれば、どれかの色について頂点の個数が足りている) ので、この色数を $k$ とする。しかし、(言わずもがな)彩色問題は非常に難しい。そこで、彩色に何らかの規則性を持たせたうえで、失敗したパターンを 2. で処理する(彩色の十分条件で捌いてやる手法)ことを考えてみる。
最も単純で雑な方法のうちのひとつとして、 DFS なり BFS なりで根から順番に $0,1,\dots,k - 1,0,1,\dots$ というように彩色していく方法がある。
ここで、以下の $2$ つの事項を思い出してほしい。
- 木に辺を $1$ つ足すと、ちょうど $1$ つサイクルが生まれる。(サイクル(の長さを求めていく感じの)方向でこの問題に取り掛かろうとするとこの着想には至りやすいかも)
- DFS木には木を構成する辺と後退辺しか存在しない。(まぁ BFS 木では余る辺の余り方が明らかにかなり嬉しくなさそうですね)
これをもとに、以下の解法が成立する。
- 適当な頂点から始め、 DFS を行う。このとき、各頂点の親を記録しておく。
- 始点からの距離が $d$ ならその頂点を色 $d \% k$ で着色する。
- 頂点 $v$ から DFS を行うときに頂点 $w$ に伸びる後退辺が発見されたとき、以下の処理を行う。
- もし $v$ の色と $w$ の色とが異なるなら、なにもしない。
- もし $v$ の色と $w$ の色とが同じなら、 2. の問題が解けている。
- 具体的には、 $v$ から $w$ に向かって DFS 木を登っていき、最後に $w$ から $v$ に直接向かうサイクルが答えになっている。
- $v$ から $w$ の頂点の色は $i,i+1,\dots,k - 1,0,1,\dots,i$ となっているので、長さが少なくとも $k+1$ であることが言え、この値は $\left \lceil \sqrt{n} \right \rceil$ 以上である。
- DFS を終えて 2. の問題が解けていない場合、 1. の問題が解けている。
- その色で塗られた頂点が最も多い色を選び、その色で塗られた頂点から $\left \lceil \sqrt{n} \right \rceil$ 個を選び出して出力すればよい。
Submission #174781388 - Codeforces
NP困難である頂点彩色とサイクル検出が結びついた非常に美しい問題。
夜にずっと考えてたら布団に入った瞬間に突然解法が降ってきたので通しました。睡眠時間を $1$ 時間ほどロストしました。
追記: 別解(次数を利用する方法)も賢かったです 本当にすごい
