Easy

問題の概要

無向単純グラフ $G=(V, E)$ に対して、 $S\subset V$ のうち $S$ による誘導部分グラフが $G$ の橋を含まないものを考える。最大の $|S|$ を求めよ。

$1\leq |V|\leq 1000, |E| \leq 1500$

まず橋を列挙する。DFSあたりでやれそうだけど実装に自信がないので愚直にやることを考えた。一本ずつ注目しながらunion findで判定すればよさそう。 $O(|E|^2\alpha(|V|))$ なので余裕。

ここでサンプルを見ると、橋の端点ではない頂点は $S$ に含めて良いこと、その残り（橋）だけをみると森になることが分かる。すると、あとは「森のうち隣接する頂点を選ばないようにしつつできるだけ多くの頂点を選ぶ」という問題を解けば良いということになる。

（ここで二部グラフ的に適当に塗れば良いという嘘を実装して時間を溶かす）

落ち着いて考えると、葉から順に選ぶか否かを決めるという方針が立ったのでやる。unordered_setに既に見た頂点か、既に選ばれた頂点かという情報を詰めながらDFSという形で実装して提出。

今思えばこれは無駄に煩雑な実装をしていて、木dpを思い出してメモ化再帰をすればよかったなあという感じです。

方針がたたないので適当にググるをすると、Binary Trieというのが見つかりました。これを使うことで多分解けるという気がしたんですが、時間内にバグを取りきれなかったので提出出来ませんでした。ざんねん。

Easyをもっとはやく解けるようにする必要がありそう。1完早解きの勝負になりやすそうな上、Medを解くにも十分な時間が要るので。