グラフ-トポロジカルソート
考え方 回答例 考え方以下がすごくわかりやすい．ゲームの後退解析（負けにしか遷移できない状態から考える）みたいな考え方． Editorial - AtCoder Beginner Contest 245 トポロジカルソートっぽく実装できる（トポロジカルソート - 競プロはじめました）．…
DAG（閉路のない有向グラフ）の辺が左から右に向くように，頂点を左から右に一列に並べる方法．「有向グラフをトポロジカルソートできなければ閉路がある」という使い方もできる．考え方 各頂点に入ってくる辺の本数（入次数，indegree）を配列indegに記録す…
無向グラフ UnionFind DFS 有向グラフ トポロジカルソート 無向グラフ【例】 ABC231D - Neighbors - 競プロはじめました UnionFindUnionFind（UnionFind木 - 競プロはじめました）を使えば，次で検出できる． 辺を張るたびに頂点をマージする 新たに$a,b$に…
【関連問題】 ABC216D - Pair of Balls - 競プロはじめました 考え方「数字を頂点」，「順序関係を辺」と考えればグラフの問題になる．求められているものは，トポロジカルソートしたもので，辞書順で最小のものであるとわかる． （トポロジカルソートについ…
【関連問題】 ABC223D - Restricted Permutation - 競プロはじめました 考え方 回答例 回答例 - カウンタで管理 回答例 - 1個ある集合・2個ある集合を別に持つ 回答例 - トポロジカルソート 考え方言われたとおりにやって間に合うというのに気付けるか，言わ…
