drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder400点 ABC-D 緑色diff 連結成分 Union-Find 連結成分ごとに分解して考える データ構造 グラフ DFS BFS 二部グラフ 二部グラフ判定 総和を求める 解空間:O(N^2)通りの選択肢 コーナーケース 考察：場合分けして考える Greedy：先に進むほど新たな選択肢が挿入される Greedy 考察：補集合を考える 【問題集】DFS・BFSのステップアップ 典型要素を詰め合わせた教育的問題 グラフ探索:頂点の値を求めていく NoviSteps1Q 一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられます。頂点番号を とします。 このグラフにおいて、以下の条件を満たす頂点の組 () の個数を答えてください。 頂点 を結ぶ辺が存在しない 頂点 を結ぶ辺を追加したグラフは二部グラフである 制約 考えたこと 二部グラフとは、下図のように、 白色の頂点同士が隣接しない 黒色の頂点同士が隣接しない という条件を満たすように、各頂点を白黒… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2022%2F12%2F23%2F223700" title="AtCoder ABC 282 D - Make Bipartite 2 (1Q, 緑色, 400 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20221223/20221223224219.png Hatena Blog https://hatena.blog 2022-12-23 22:37:00 rich https://drken1215.hatenablog.com/entry/2022/12/23/223700 1.0 100%