二部彩色と成分構造を扱う
概要
二部グラフの彩色と成分構造
無向グラフを二色に塗れる条件を探索で検証し、各連結成分の二部サイズ・反転対称性を集約する。
考え方
各辺の両端が違う色になるよう成分ごとに2色へ塗る。同色を要求する辺が見つかれば奇閉路の存在と対応して二部性が破れる。二部性の判定から左右の役割を持つmatchingへ進める。
各未訪問頂点を色0で開始し、辺u−vで未訪問vにはcolor[v]=1−color[u]を付け、訪問済みなら両色が異なるかを検査する。同じ色が見つかると、DFS/BFS木上の共通祖先までの道とその辺で奇閉路ができる。矛盾がなければ全辺が異色になり二部性を証明できる。各成分で色0・1の個数を数える。
連結成分のある頂点の色を固定すると、その全隣接色は強制され、全頂点へ伝わる。従って色付き表現は成分ごとの反転2通りだけで、C成分の非空graphには2^C通りある。ラベルの付いた頂点上で彩色を忘れる計数なら、この自由な反転による重複を補正できる。左右の役割・サイズを固定する問題では、反転しても同じ有効対象とは限らないため、無条件に2^Cで割らない。
成立条件と計算量
BFS・DFSでO(V+E)。非連結成分では色の左右を独立に反転できるため、数え上げで対称性を扱う。自己loopは即矛盾。無向graphの二部性を、有向辺の向きだけで決めない。
問題一覧
- ABC451 F「Make Bipartite 3」 公式問題
技能・出典
主題: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / small-to-large・DSU on Tree(小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 二部グラフの彩色と成分構造 / 補助タグ: DSUによる連結成分管理・縮約、small-to-large・DSU on Tree
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC327 G「Many Good Tuple Problems」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 二部彩色と成分構造を扱う(連結二部グラフの二つの彩色が部の交換だけで対応することを使い、彩色付きの計数から同じグラフの重複を補正できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 二部グラフの彩色と成分構造、組合せ係数・数え上げ、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC398 E「Tree Game」 公式問題
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 二部グラフの彩色と成分構造、偶奇不変量によるゲーム戦略 / 補助タグ: 対話protocolとquery設計
- ABC398 G「Not Only Tree Game」 公式問題
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。 - ABC437 G「Colorful Christmas Tree」 公式問題主題: 最大流・最小カット
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。 二部彩色を前提に、頂点・色組の使用回数A_{v,k}を容量へ写す最大流のモデルを学ぶ。流量N−1から各木辺の削除時の色対を固定する。一対一matchingではない。次に、実行可能な辺がないと仮定して葉から根へ条件を伝播させると矛盾することを示す。一辺削除した後も残りの回数制約が保たれるため、この存在証明を帰納的に繰り返して操作列を復元できる。静的な割当の可否と時系列の実行可能性を別々に証明する。主タグ: 最大流・最小カット / 補助タグ: 二部グラフの彩色と成分構造、構成解・witness復元
- ABC445 G「Knight Placement」 公式問題
技能・出典
主題: 二部matching・Hall・Kőnig(左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。) / gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。主タグ: 二部matching・Hall・Kőnig / 補助タグ: 二部グラフの彩色と成分構造、gcd不変量・差分構造
- ABC454 E「LRUD Moving」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。主タグ: 構成解・witness復元 / 補助タグ: 二部グラフの彩色と成分構造
前提・学習成果・出典
習得対象の目安: 緑色(800–1199)。二部性と部の反転対称性を扱い、連結二部グラフの彩色重複も補正する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bipartite-structure
習得する技能
- 連結二部グラフの二つの彩色が部の交換だけで対応することを使い、彩色付きの計数から同じグラフの重複を補正できる。
- 各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 二部matching・Hall・Kőnig。
無向グラフを探索できることを前提に二部性と部の交換対称性を扱い、連結二部グラフの彩色重複も補正する。
このUnitでは扱わないもの
- 重み付き最短路、一般の彩色問題、および容量付きmatching・min-cutの最適化。