グラフ-DFS

ABC315E - Prerequisites

考え方 回答例 考え方DFSで帰りがけを見る. スタックで実装できる. 【関連】 非再帰 Euler Tour を Python でやる - Qiita ABC284E - Count Simple Paths - 競プロはじめました回答例DFSをするためのseenと,すでにansに加えたかを管理するseen2を使った.…

ABC292E - Transitivity

考え方 回答例 考え方アライグマ「E問題は、要するに「直接辺で繋がってないけど移動できる頂点の組の個数」を求める問題で、「移動できる頂点の組-辺の個数」なのだ! 全部の頂点からDFSすれば求められるのだ!」— 競技プログラミングをするフレンズ (@kyo…

ABC284E - Count Simple Paths

考え方 回答例(スタックでDFS) 回答例(再帰でDFS) 考え方DFSでできる.頂点に入ったときにフラグを立て,頂点を抜けるときにフラグを消す.回答例(スタックでDFS)頂点に入ったときと抜けるときは,行きがけと帰りがけに対応する.スタックを使って行き…

ABC251F - Two Spanning Trees

考え方 回答例 考え方入力例として, 3 3 1 2 2 3 3 1を考えると,DFSで辺を作れば$T_{1}$に,BFSで辺を作れば$T_{2}$になることがわかる.すでに頂点をつないだかどうかはsetで管理すれば良い.回答例スタックを使えばDFSになり,キューを使えばBFSになる.…

ABC220F - Distance Sums 2

考え方 回答例(再帰関数) 回答例(スタック) 考え方AtCoder Beginner Contest 220 - YouTube 頂点1からの答えがわかっていれば,頂点1に隣接する頂点$v$の答えは「(頂点1の答え) - ($v$の部分木の頂点数) + (N - $v$の部分木の頂点数)」で求められる.こ…

ABC231D - Neighbors

考え方 回答例 UnionFind DFS 考え方「$A$と$B$が隣あっている」を「$A$と$B$に辺がはられている」と読み替えればグラフの問題になる.横一列に並べられる条件は, すべての頂点から出ている辺の本数が2以下であること 閉路がないこと である.閉路検出は次…