【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【Union-Find】

2021.01.02

この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。

Union-Find について以下の文献が参考になります。

Union-Find の計算量について、私は読んでいませんが、以下の文献が参考になるかもしれません。

計算量を表す際に出てくるアッカーマン関数やその逆関数については以下の文献が参考になります。

以降では Union-Find の実装は AtCoder Library の DSU を用います。また、\alpha(n) をアッカーマン関数 A(n, n) の逆関数とします。

85. DSL_1_A – 互いに素な集合

Union-Find の使い方を覚える問題です。AtCoder Library の DSU のメンバ関数 merge を問題文の unite に、same を same に対応させてシミュレーションすれば解答できます。

計算量は O(q \alpha(n))<O(q \log n) = 10^7 程度です。実行時間制限に違反せずに解答できます。

86. AtCoder Beginner Contest 075 C – Bridge

問題文の橋の定義通りに、辺ごとに元のグラフから取り除いてできるグラフが連結であるか判定して、橋を数えることを考えます。

AtCoder Library の DSU を使う場合、以下の手順で連結か判定できます。

  1. 取り除く辺以外を DSU に追加します。
  2. 任意の点 ( 例えば点 1 ) の属する連結成分の大きさをメンバ関数 size で計算し、連結成分の大きさが N であれば連結、N より小さい場合は非連結と判定します。

判定方法について補足します。
グラフが連結である場合、連結成分は 1 つです。N 個のすべての点がその連結成分に属しているため、任意の点が属する連結成分の大きさは N になります。
裏を考えます。グラフが非連結の場合、任意の点に対し、経路が存在しない点が少なくとも 1 つ存在します。そのため、任意の点について、その点が属する連結成分の大きさは N よりも小さいです。
以上より、以下の 2 つが同値であることを確認できるため、上記の判定方法で問題ありません。

  • 任意の点の属する連結成分の大きさが N である。
  • グラフが連結である。

1 回の判定の計算量は O(M \alpha (N)) です。全体の計算量は O(M^2 \alpha(N))<O(M^2 \log(N)) = 10^5 程度です。実行時間制限に違反せずに解答できます。

グラフの連結性の判定は深さ優先探索や幅優先探索でも可能です。以下の記事が参考になります。

上記の記事の要領で連結成分の個数が 1 になる場合は連結であると判定すればよいです。

深さ優先探索や幅優先探索で判定する場合は 1 回の判定の計算量は O(M + N) になります。全体の計算量は O(M (M + N)) になります。

87. AtCoder Beginner Contest 120 D – Decayed Bridge

橋が崩落するたびに橋のグラフを作成して、頂点ごとに深さ優先探索などで行き来できる頂点とできない頂点を探索する場合、計算量は \Omega(M (M + N)) = 10^{10} 程度になります。実行時間制限に違反しそうです。

まず、各時点のグラフを効率よく計算する方法を考えます。
多くの場合、グラフに辺を追加する処理はグラフから辺を削除する処理に比べて簡単です。そこで、すべての橋がある状態から 1 つづつ橋が崩壊する問題を、橋が全く無い状態から 1 つづつ橋が架かる問題に変換します。橋 (A_i, B_i) を逆順に並べて、(A_i, B_i) を橋のグラフに追加しながら、不便さを計算し、最後に不便さを逆順に出力するとすれば答えを変えずに問題を変換できます。

次に不便さを効率よく計算するために 1 つ前の不便さから計算することを考えます。
新たに橋 (A_i, B_i) が架かるとします。架かる前に A_i と B_i の間で行き来できた場合は不便さは変わりません。一方で橋が架かって初めて、A_i と B_i の間で行き来きできるようになったならば、A_i と行き来できた島と B_i と行き来できた島の組み合わせの分だけ、不便さが減ります。
つまり、\mathrm{dp}[i] を i 番目までの橋が架かった時点の不便さ、C[i][a] を i 番目までの橋が架かった時点での島 a と行き来できる島の個数 (すなわち a の属する連結成分の大きさ) とすると以下の更新式が成り立ちます。

\mathrm{dp}[i + 1] = \begin{cases}
\mathrm{dp}[i]&(A_i \text{と} B_i \text{で行き来できていた}) \\
\mathrm{dp}[i] – C[i][A_i] C[i][B_i]&(A_i \text{と} B_i \text{で行き来できていなかった})
\end{cases}

橋のグラフの連結成分を AtCoder Library の DSU で管理する場合、以下はならし O(\alpha(N)) の計算量でできます。

  • 辺の追加
  • 点と点の連結の判定
  • 点が属する連結成分の大きさの算出

橋が 1 つも架かっていないときの不便さ \mathrm{dp}[0] は任意の 2 つの島の組み合わせであるため、_N C_2 = N (N – 1) / 2 になります。

各時点で必要な計算がならし O(\alpha(N)) でできるため、全体の計算量は O(M \alpha(N))<O(M \log N) = 10^7 程度になります。実行時間制限を満たして解答できます。