ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ 概要 LIbrary Checker のジャッジをお借りして、次の 3 種類の強連結成分分解アルゴリズムそれぞれの、いくつかのバージョンの速度を比較します。 Kosaraju's algorithm Tarjan's algorithm Gabow's algorithm その結果、Vec<Vec<usize>> を構築して行う Kosaraju's algorithm は、この記事の最速実装に比べて $3$ 倍程度遅いことがわかりました。 今回の計測では最速の座は Gabow's が手にしましたが、Kosaraju's の高速な実装もそれとほぼ変わりませんでした。従って実装の短さを考えると … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2024%2F12%2F10%2F011904" title="3 種類の強連結成分分解アルゴリズムや、そのバリエーションの速度比較 - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2024-12-10 01:19:04 rich https://blog.ngtkana.com/entry/2024/12/10/011904 1.0 100%