ABC 226 E — Just one

考察

各頂点の出次数を1にすると、連結成分内の出次数総和は頂点数V'、一方で各無向辺は向きを一つ持つので総和は辺数E'である。したがって成分ごとにV'=E'が必要になる。連結成分でE'=V'ならちょうど一つの閉路を持つ単一サイクル付き木であり、次数1の頂点から出る唯一の辺は外向きに強制される。葉とその強制辺を繰り返し除くとサイクルだけが残り、各頂点の出次数を1にする向きはサイクルを一周する二方向だけである。

採用する候補: DFSで各連結成分の頂点数と辺数を数え、全成分が単一サイクルを持つV'=E'なら成分ごとの2方向を掛け合わせる。

V'=E'の連結グラフは葉を剥がすと一つのサイクルになり、木部分の向きは強制、サイクルだけが時計回り・反時計回りの2択になる。

棄却する候補: M本の辺の向きを2^M通り列挙し、各頂点の出次数を検査する。

Mは2×10^5まであり、成分構造を使わない指数列挙は不可能である。

未訪問頂点からDFSを行って成分のV'と次数和/2のE'を求め、不一致が一つでもあれば0、全て一致するなら2^(連結成分数)を998244353で返す。

典型の発動条件

連結成分ごとの独立な数え上げ

発動条件: 辺の制約と選択が連結成分をまたがず、全体の方法数が成分ごとの積になるとき。

各成分の実現可能性と方法数を別々に求め、不可能判定または積へ集約する。

単一サイクル連結成分の判定

発動条件: 連結無向グラフで頂点数と辺数が等しいという条件が現れるとき。

E=Vから閉路数が一つと判断し、葉を剥がした核がサイクルになる構造を使う。

問題固有の要素

『各頂点からちょうど一本』を全頂点で足すだけで、向き付けを考える前に成分ごとの辺数=頂点数という強い必要条件が得られ、それが十分条件にもなる。

別の問題へ持ち帰る視点: 局所次数条件は成分内で総和を取り、辺が何回数えられるかと比較して先にグラフ構造を絞る。

正当性

各頂点の要求向きで成分辺数が頂点数と一致することが必要。連結V=Eはunicyclicで木枝の向きは葉から強制。cycleだけ二方向が可能で全要求を満たし二通り。成分は独立なので不一致なら0、全一致なら2^C。

実装上の注意

  • 無向辺を隣接リストで二回数える場合は次数和を2で割る。孤立頂点を含む成分もV'≠E'として正しく0にする。

復習の核

  • 全頂点の次数条件はまず成分内で足し、EとVの関係が木・単一サイクル・多重サイクルのどれを強制するかを見る。

計算量と制約

時間

N頂点M辺。成分DFS O(N+M)、累積二倍O(N)。

空間

隣接とvisited O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1 \leq M \leq 2\times 10^5; 1 \leq U_i,V_i \leq N; U_i \neq V_i; All values in input are integers.; The given graph is simple.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Just one の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単一サイクル成分とgraph core

主題
  • 単一サイクル成分とgraph core: 連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 単一サイクル成分とgraph core

    補助タグ: 法上の四則演算・高速累乗・逆元

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 単一サイクル成分とgraph core

    • 連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題