アルゴリズム/深さ優先探索

APC001 D: Forest

apc001.contest.atcoder.jp 解き方 前提 n個の木を連結にするためには、n-1個の辺を追加する必要がある 条件から辺に含まれる頂点は重複しないので、2n-2個の頂点が辺に含まれる 連結にするためには、各木から少なくとも1つは頂点を選ばないといけない 実装 …

ABC075 C: Bridges

C - Bridge 解き方 DFSして橋を数える ハマったところ bridgeを見つけるアルゴリズムを忘れていたので、一から書いてたらデバッグに時間かかった github.com

ARC079 F: Namori Grundy

arc079.contest.atcoder.jp 解き方 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ 閉路とそれ以外にまず分ける 閉路以外の部分は、根を0、その上を…としていくと一意に定まる 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算…