グラフの橋と関節点の効率的な判定LowLink法の解説 - Senの競技プログラミング備忘録

LowLinkを実装してみた。自分用の詰まった部分のメモも含む。 どういう問題をやるの グラフが与えられて 関節点 その点を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる) 橋 その辺を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる) これを求める。 Union-Findでつながってるかどうかを$ O(V + E) $で判定できるので、 抜く頂点や辺を全通り試せば、$ O(V(V + E)), O(E(V + E)) $の計算量になる。 LowLinkという手法を使うことで、$ O(V + E) $にとどめることができる。 LowLinkのきもち 先行記事たち。ここら辺を見ながらこれをサブノートとして見る方がいい。 ei1333さん アルゴリズムロジック DFSしながら、ループを構成してるものに全部同じ番号を割り当てることで、ループ内なら基本的に点や辺抜いて