考察
集合 K_i 内へ重み C_i の clique を張ると辺数は二乗になるが、同じ重みの clique 内では一頂点を中心とする K_i−1 本だけで全頂点を同重み以下で連結できる。Kruskal 法では、ある辺の両端がその辺以下の重みの別 path で既に結ばれるなら、その辺を候補から除いても MST 重みは変わらない。star path は二辺かかっても MST の目的は辺数でなく重み総和であり、cycle property により同重み clique 辺を削除できる。全候補処理後に DSU component が一つでなければ、元の全 clique graph でも連結不能なので −1 である。
採用する候補: 各 clique を任意の代表と他頂点を結ぶ star K_i−1 辺へ縮約し、全 star 辺へ Kruskal 法を適用する。
削除した clique 辺は同じ重みの star path で代替でき、候補辺総数が ΣK_i に落ちる。
棄却する候補: 各集合内の全頂点対に辺を生成して通常の Kruskal 法を行う。
一集合 K_i=N のとき Θ(N²) 辺となり、ΣK_i≤4×10^5 という入力サイズ保証を活かせない。
各操作 i について A_{i,1} と A_{i,j}(j≥2) の辺 (C_i) だけを生成する。重み昇順に sort し、DSU で異 component を結ぶ辺の重みを加算する。採用辺が N−1 本なら総和、そうでなければ −1 を出す。
典型の発動条件
密な同重み clique の sparse certificate
発動条件: 暗黙に追加される完全グラフの全辺が同じ重みで、連結性だけが重要なとき。
任意 spanning tree だけ残し、同重み path を代替証明にする。
Kruskal 法と cycle property
発動条件: 辺候補を安全に削減して MST を求めたいとき。
辺以下の重みで端点を結ぶ別 path がある辺を除外する。
問題固有の要素
clique の完全な隣接情報は不要で、MST に必要な「同コストで集合内を連結できる証明書」は star で十分である。
別の問題へ持ち帰る視点: 暗黙 dense graph では、目的関数が保持される sparse certificate をまず探す。
正当性
同cost cliqueを同cost starへ変えても各閾値の連結成分が同じ。MSTのKruskal選択数は各重み閾値の連結性で決まるため最小costも不変。生成starのMSTを得れば元cliqueでも同cost接続を実現できる。
実装上の注意
- star の中心は集合内ならどれでもよく、同重み辺の sort 順は任意。総重みは最大10^9(N−1)なので 64 bit を使う。
復習の核
- 「二辺の代替だから高くなる」と誤解せず、Kruskal の時点で同重み連結になっていることを考える。縮約後の連結性も確認する。
計算量と制約
時間
N頂点、操作M、所属総数L=ΣK_i。生成辺O(L)、Kruskal O(L log L+Lα(N))。
空間
star辺とDSU O(N+L)。
制約との対応
公式制約の確認範囲: 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; 2 \leq K_i \leq N; \sum_{i=1}^{M} K_i \leq 4 \times 10^5; 1 \leq A_{i,1} < A_{i,2} < \dots < A_{i,K_i} \leq N; 1 \leq C_i \leq 10^9; All input values are integers.
出典