連結グラフには全域木が必ず存在する

計算量

• 頂点の数を $N$、辺の数を $M$ とする
  • 辺の重みでソート: $O(M \log M)$
  • UF を使ったメインの部分: $O(M \alpha(N))$
    • $\alpha$ はアッカーマンの逆関数

問題

• ABC352 E - Clique Connect
• $K$ 本の辺を選んで、重み最小の部分森を作る (Q3. K 本の辺を選ぶ | アルゴ式)
• どの最小全域木にも含まれているような辺の本数（Q5. 絶対使う辺 (2) | アルゴ式）
• 各辺はある最小全域木に含まれているか？
• Q6. グリッドグラフ (2) | アルゴ式

  • 平面上のすべての領域にいけるように辺を除去するとき、除去した辺の重みの総和の最小は？

    

    • 入力は左右の辺の重みが $(W-1)\times H$ 個、上下の辺の重みが $W \times (H-1)$ 個与えられる

  • 双対グラフ（面を頂点としたグラフ）を考える

    • 双対グラフについては グラフ を参照
    • すべての領域に行けるというのは閉路がないってこと

証明

• 「縮約」が使える？
  • Q2. 最小全域木 | アルゴ式 (解説)
  • ‣

最小全域木の応用

知りたい（最小全域木が求まると何が嬉しい？）

• ABC394 G - Dense Buildings