考察
各頂点の出次数を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.
出典