二部グラフ判定
AtCoder
AtCoder400点
ABC-D
緑色diff
連結成分
Union-Find
連結成分ごとに分解して考える
データ構造
グラフ問題
DFS
BFS
二部グラフ
二部グラフ判定
総和を求める
O(N^2)個のものを考える問題
コーナーケース
場合分け
端から順に決まって行くGreedy
Greedy
補集合を考える
そのまま覚えたい典型問題
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある! その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる!! 問題へのリンク 問題概要 頂点数 、辺数 の単…
Codeforces
CodeforcesCombined
CodeforcesR2700
グラフ問題
二部グラフ判定
二部グラフ
牛ゲー
緩和しても良い
Floyd-Warshall法
最短路問題
復元
1つ求める
Yes/No判定問題
必要条件を列挙したら十分条件になる
個人的要復習
差分制約系
最大値と最小値の差の最小化
ある量を固定して考える
なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…
Codeforces
グラフ問題
クエリ処理問題
O(N^2)個のものを考える問題
二部グラフ
二部グラフ判定
Union-Find
グラフの頂点を倍加する
DP状態:あまり
クエリ:削除
色に関する問題
ならし計算量解析
undoつきUnion-Find
CodeforcesDIV1-C
CodeforcesR2500
undo 付き Union-Find ってなんぞ!? 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…