アルゴリズム

橋(bridge)検出アルゴリズム

連結グラフにおいて橋(bridge)とは、それを取り除くと連結でなくなってしまうような辺のこと。閉路に含まれない辺が橋になる。 橋はDFSを行うことで検出することができる。DFSは、アルゴリズムの一部としてグラフの構造を調べる時によく使われる。 アルゴ…

Codeforces Round #206 (Div. 2)

Codeforcesに初参加したので感想を書きます。 A 難易度の基準がわからなかったので、定義を見てかなりビビった。でも、他の人達が即答しているのを見て、見掛け倒しの問題なのだとわかった。 B 簡単な場合分け。 最高でもc4を払えば十分。busに払う額をmax_b…