ABC 213 G — Connectivity 2

考察

頂点集合 S の内部にある元グラフの辺数を e(S) とすると、S 上で選べる全ての部分グラフは各辺を選ぶか否かで 2 の e(S) 乗個ある。

頂点 1 と頂点 k が連結である部分グラフは、頂点 1 を含む連結成分 S を一意に取り出すことで分類できる。

棄却する候補: 元グラフの各辺を使うかどうか全て列挙し、そのたびに頂点 1 から連結性を調べる。

辺数に対して指数個の部分グラフがあり、M が大きい制約では列挙できない。

採用する候補: 頂点部分集合ごとに、その集合全体を連結にする辺選択数を、頂点 1 側の連結成分を固定する包除型の部分集合 DP で求める。

N が小さいことを利用し、辺部分集合ではなく頂点部分集合とその部分集合の列挙へ計算対象を移せる。

連結グラフ数 f(S) は全グラフ数から、固定した基準頂点を含む真部分集合 T がその連結成分になる場合を全て引けば得られる。

基準頂点を T に必ず含めることで、非連結グラフを基準頂点の連結成分によりちょうど一度だけ数えられる。残りの頂点集合は S∖TS\setminus T であり、そこでの辺選択は 2e(S∖T)2^{e(S\setminus T)} 通りである。

各頂点集合の内部辺数から全部分グラフ数 2e(S)2^{e(S)} を作り、基準頂点の連結成分による再帰で連結数を求めた後、1 と k を含む成分 S と外側の自由な辺選択を合成する。

典型の発動条件

連結成分を固定する数え上げ

発動条件: 全グラフの数は容易だが、頂点集合全体が連結な場合だけを数えたいとき。

基準頂点を含む連結成分 T を一意な証人として、全グラフ数から非連結な場合を差し引く。

部分集合 DP と部分集合列挙

発動条件: 頂点数は小さく、集合 S ごとにその部分集合 T を走査する再帰が自然に現れるとき。

ビット集合 S の真部分集合 T のうち基準頂点を含むものを列挙し、連結成分と残りのグラフ数を掛ける。

問題固有の要素

頂点 1 の成分が S と決まると、S と外部を結ぶ辺は全て不使用でなければならず、外部内部の辺だけが自由に選べる。

別の問題へ持ち帰る視点: 特定頂点の連結成分で対象を分類するときは、成分内部・成分外部・境界をまたぐ辺の三種類へ分けて自由度を数える。

正当性

各部分グラフの基準頂点の連結成分Tは一意である。内部はf(T)通り、補集合内部は2^{e(S\T)}通り、境界辺は不採用に固定する。この分類で非連結分を全グラフ数から引くとf(S)を得る。同様に1とkを含む成分Sを合計すればその二頂点が連結なグラフだけを一度数える。

実装上の注意

  • f(S) の再帰では S 内の固定頂点を一つ選び、T はその頂点を含む真部分集合だけに限定する。
  • 各集合の内部辺数と 2 の冪を事前計算し、減算結果を法 998244353 の範囲へ正規化する。

復習の核

  • 連結性の数え上げでは、非連結な対象を一意に代表する「固定頂点を含む成分」を先に選ぶ。
  • 最終式で S の外側を自由に数える前に、境界辺が不使用で固定される理由を成分の最大性から確認する。

計算量と制約

時間

O(3^N+N²2^N)。

空間

O(2^N+N²)。

制約との対応

公式制約の確認範囲(時間制限3秒、メモリ制限1024 MiB):

  • 2≤N≤172 \leq N \leq 17
  • 0≤M≤N(N−1)20 \leq M \leq \frac{N(N-1)}{2}
  • 1≤ai<bi≤N1 \leq a_i \lt b_i \leq N
  • i≠ji \neq j ならば (ai,bi)≠(aj,bj)(a_i, b_i) \neq (a_j, b_j)
  • 入力はすべて整数

出典

分類・前提・執筆情報

掲載状態: 収録済み

Connectivity 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: label付き連結成分分解・exponential formula

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: label付き連結成分分解・exponential formula

    補助タグ: 部分集合・bitmask状態DP

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

    学習の位置

    体系上の位置: label付き連結成分分解・exponential formula

    • 最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。

    先に読む単元:

    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。
    • 組合せを生成関数へ符号化する — 高速畳み込みを前提にせず、係数の意味を定義して和・積・sequence・set・cycleが表す組合せ構造を欲しい係数へ翻訳する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題