ABC 420 E — Reachability Query

考察

edge追加だけの無向graphではconnected componentsはmergeするだけで分裂せず、type3の答えはvのcomponent内にblack vertexが一個以上あるかだけで決まる。各vertexの色toggleはその時点のrootが持つblack countを±1すればよく、merge時は二componentのcountを加算できる。toggle対象vのcomponent代表は過去のunionで変わり得るので、保存した古いrootではなく毎回find(v)してblackCountを更新する。union by size/rankで新rootを決めた直後に二rootのblackCountを足せば、個々のblack vertexを移し替えずcomponent aggregateを保てる。

採用する候補: componentごとのblack vertex数を追加情報として持つDSU

type1はunion時にsizeとblackCountを合成、type2はcolor配列を反転してfind(v)のcountを更新、type3はroot count>0を判定する。各queryほぼ定数時間。

棄却する候補: type3ごとにvからBFSしてblack vertexを探す

Q=6×10^5で大componentを何度も走査しO(NQ)になり得る。edge削除がないためcomponentを再探索する必要はない。

parent,size,blackCount,colorを初期化する。type1(u,v)はrootsが異なればunionしてcount和を新rootへ置く。type2(v)はr=find(v)としてwhite→blackならcount[r]++、逆なら--しcolorを反転。type3(v)はblackCount[find(v)]>0ならYes。

典型の発動条件

augmented DSU

発動条件: merge-only componentに対する集計値queryとvertex属性更新があるとき。

rootにblack数を持ち、unionで加法mergeする。

component aggregate

発動条件: queryがcomponent内の存在判定で、要素ごとのboolean和で表せるとき。

black存在をblack count>0へ置き換える。

問題固有の要素

DSUのconnectivityだけでなく、toggle可能な頂点属性の総数をrootへ持たせればcomponent存在queryまで同じ構造で処理できる。

別の問題へ持ち帰る視点: merge可能aggregateに加えて要素更新があるDSUでは、更新時に現在rootへ差分を入れればよい。

正当性

黒数を成分内の黒頂点数とする不変条件は union の加算と toggle の±1で保たれる。到達可能集合は現在の成分だから、find(v) の黒数が正であることが質問の必要十分条件。

実装上の注意

  • 同component内へのedge追加ではcountを二重加算しない。toggle前のcolorを保持し、path compression後のrootへ±1する。

復習の核

  • isolated vertexのtoggle、同component内edge追加、black頂点を含む二componentのmerge、最後のblackをwhiteへ戻す例を愚直component探索と比較する。

計算量と制約

時間

N 頂点、Q 操作で O((N+Q)α(N))。

空間

DSU、色と成分黒数で O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1 \le N \le 2 \times 10^5; 1 \le Q \le 6 \times 10^5; Type 1 queries satisfy the following constraints: 1 \le u < v \le N For each query, no edge connecting u and v has been added before that query.; 1 \le u < v \le N; For each query, no edge connecting u and v has been added before that query.; Type 2,3 queries satisfy the following constraints: 1 \le v \le N; 1 \le v \le N

出典

分類・前提・執筆情報

掲載状態: 収録済み

Reachability Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DSUによる連結成分管理・縮約

主題
  • DSUによる連結成分管理・縮約: 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DSUによる連結成分管理・縮約

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

      学習の位置

      体系上の位置: DSUによる連結成分管理・縮約

      • 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題