atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ データ構造 グラフ理論 連結性 Union-Find アッカーマン関数 逆アッカーマン関数 1. 概要 本記事では，Union-Find の計算量が $\mathrm{O}\left(N+Q\alpha(N)\right)$ であるという事実を証明します． この事実は競技プログラミングユーザーの多くが知っている非常に有名なものだと思いますが，Union-Find の基礎的な動作原理や，計算量 $\mathrm{O}(N+Q\log N)$ であることの理解に比べて非常に難しくなるため，多くの解説でも省略されており，証明を学んだことがないユーザーもかなり多いと思います．ぜひこの機会に学んでみてください． 2. 前提知識 Union-Find のアルゴリズムの基本的な仕組みを理解している… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Funionfind_complexity" title="Union-Find の計算量上界 - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:09:15 rich https://info.atcoder.jp/entry/algorithm_lectures/unionfind_complexity 1.0 100%