drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces グラフ クエリ処理問題 解空間:O(N^2)通りの選択肢 二部グラフ 二部グラフ判定 Union-Find グラフテク:頂点を倍加する DP状態:あまり 操作:削除 色に関する問題 ならし計算量解析 undoつきUnion-Find CodeforcesDIV1-C CodeforcesR2500 undo 付き Union-Find ってなんぞ！？ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色 の頂点と色 の頂点のみからなる部分グラフを考えたとき、その部分グラフが二部グラフである 制約 考えたこと 単純に全色ペアについて二部グラフ判定したのでは の計算量がかかりそう。 少し工夫すると、ダメになる可能性のある色のペアは、両端点の色が異なるような辺 の両端の色だけであることに注目して、次のようにできる。 各色 に対してその… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F11%2F02%2F201400" title="Codeforces Round #680 (Div. 1) C. Team-Building (R2500) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-11-02 20:14:00 rich https://drken1215.hatenablog.com/entry/2020/11/02/201400 1.0 100%