ABC 372 E — K-th Largest Connected Components

考察

問い合わせる順位は高々10なので、各連結成分の頂点番号を全て保持する必要はない。大きい方から上位10個だけ残せば、どの順位の問い合わせにも答えられる。さらに辺追加で成分を併合しても、既に10個の大きい頂点がある要素が、上位10個へ入ることはない。

問い合わせる順位を kk、問い合わせられる最大の順位を BB と定める。本問では 1≤k≤B=101\leq k\leq B=10 である。順位は1始まりで数え、保持するのは1位から BB 位まで、捨てるのは B+1B+1 位以降とする。頂点数が BB 未満の成分では全頂点を残す。

境界を見るため、独自例として B=2B=2 に縮め、ある成分の頂点番号を降順に並べると (9,7,4)(9,7,4) になる場合を考える。残すのは (9,7)(9,7) であり、捨てるのは3位の4だけである。別の成分 (3,2)(3,2) と併合しても上位2個は (9,7)(9,7) のままなので、元の2位である7を先に捨ててはいけない。一方、4より大きい9と7は併合後も同じ成分に残るため、4が上位2個へ戻ることはない。

そこでDSUの各根に、成分の頂点番号の上位 BB 個を降順列として持たせる。異なる成分を併合するときは、二列の先頭どうしを比べて大きい方を取り出す二ポインタのマージで、新しい降順列を作る。BB 個を取り出すか、両列を使い切ったら止めればよい。片方を使い切ったら他方の残りから取り出す。両成分の上位列だけから併合後の上位列を復元できるため、全頂点の集合を持つ方法より更新が小さく済む。

初期状態では、各頂点をその頂点番号だけの一要素列で初期化する。タイプ1では両端の根を求め、同じ根なら何もしない。異なる根なら、二つの上位列をマージし、DSUの併合後に残る根へ保存する。DSUは成分サイズの小さい側を大きい側へ付け、代表の探索には経路圧縮を使う。

タイプ2では、指定頂点の現在の根のリストを調べる。長さが kk 未満なら -1、そうでなければ0始まり添字 k−1k-1 の頂点番号を返す。代表を求めた後の答えの取り出しは O(1)O(1) で済む。

典型の発動条件

DSU への要約情報の付加

発動条件: 辺追加だけの動的連結性で、成分ごとに結合可能な要約情報を答えたいとき。

問い合わせの最大順位が小さく、捨てた要素が将来も上位へ戻らないなら、成分の上位の要素だけを根に保持し、併合と同時に結合する。

問題固有の要素

本問の k≤10k\leq 10 という制約により、各成分で上位10個だけを保持すればよい。辺の追加だけで頂点が成分から抜けないことが、捨てた要素を復活させずに済む理由である。

別の問題へ持ち帰る視点: 成分情報を DSU に載せる際は、併合後も必要情報が子の要約だけから復元できるかを確認する。

正当性

各根のリストは、その成分の頂点番号を大きい順に最大 BB 個、重複なく並べたものとする。初期状態の成分は一頂点だけなので、この条件を満たす。

ある成分で B+1B+1 位以降にある頂点には、その成分内に自分より大きい頂点が少なくとも BB 個ある。辺追加による併合では、それらの頂点は一つも失われない。従って、その頂点の順位は併合後も B+1B+1 位以降であり、将来の上位 BB 個には入らない。一方、BB 位の頂点より大きい頂点は B−1B-1 個しかないため、同じ理由で捨てることはできない。

よって、異なる二成分の併合後に上位 BB 個へ入る頂点は、必ず併合前のどちらかのリストに含まれる。両リストは頂点集合が重ならず、それぞれ降順なので、大きい順に最大 BB 個をマージすれば新しい成分でも条件が保たれる。同一成分への辺追加では頂点集合が変わらないため、リストを更新しない。これにより同じ頂点を二重に数えることも防げる。

以上から、全操作後も各リストは正しい。k≤Bk\leq B なので、リストに kk 個以上あれば添字 k−1k-1 が求める頂点番号であり、kk 個未満なら成分全体にも kk 個の頂点がないため -1 が正しい。

実装上の注意

  • 両端が既に同一成分なら、リストを二重に混ぜない。異なる成分なら、両リストとも BB 位までをマージの候補に含める。
  • 問い合わせの順位は1始まり、配列の添字は0始まりである。k=10k=10 では10個目を残して添字9を参照し、リスト長が10未満なら -1 とする。
  • 併合後は現在の根のリストだけを参照する。吸収された根に古い列が残っていても、それを問い合わせや次のマージに使わない。

復習の核

  • 上位 BB 個を残すなら、捨てるのは B+1B+1 位以降。既に BB 個の大きい要素があり、その要素が今後も失われないことを確認する。

計算量と制約

時間

頂点数を NN、操作数を QQ とする。初期化は O(N)O(N)。サイズによる併合と経路圧縮を使うDSUの操作は償却 O(α(N))O(\alpha(N))、上位列のマージは1回 O(B)O(B) なので、全体は O(N+Q(α(N)+B))O(N+Q(\alpha(N)+B)) である。α\alpha は逆Ackermann関数を表す。

空間

DSUの配列と、各頂点に最大 BB 個分の上位列を確保しても、安全な上界は O(NB)O(NB) である。入力は1操作ずつ処理できる。

制約との対応

公式制約は 1≤N,Q≤2×1051\leq N,Q\leq 2\times 10^5、1≤k≤101\leq k\leq 10。時間制限は2秒、メモリ制限は1024 MiBである。B=10B=10 とすれば、各併合で取り出す要素は高々10個となる。全頂点の再走査や集合全体のソートは不要である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

K-th Largest Connected Components の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題