更新記録

2022 年 2 月 1 日：投稿
2022 年 4 月 3 日：用語「 CSR 形式」を使うように記事全体を改変

要約

$10^5$ 頂点以上の静的グラフの隣接リスト表現を CSR (Compressed Row Storage) 形式で管理すると、ベクタのベクタに比べて利便性をほぼ失わず 100ms 程度の高速化、省メモリを達成できます。とてもおすすめです。

本文

競技プログラミングではかなりの頻度で頂点数が $10^5$ 以上の静的なグラフを扱います。このような場合、ほぼ必ず各頂点の隣接リストを作成します。このとき C++ の平易なプログラムでは vector<vector<int>> や vector<int>[] がよく用いられますが、これを $1$ 次元配列による表現に書き換えることで例えば 100 ミリ秒程度の高速化を見込めます。 vector<int> が定数個になるため、メモリ使用量も改善します。

vector<vector<int>> からの移行を考えると、辺重み無しの隣接リストのインターフェースは次のようになるでしょう。

(コンストラクタ) ：辺のリスト vector<pair<int,int>> や隣接リスト表現 vector<vector<int>> を主な入力とし、隣接リストを構築する。
operator[](int i) ：頂点 $i$ に隣接する頂点のリストを表すオブジェクトを返す。今回は vector を返せないので、代わりに begin , end を扱える別の構造体を返す。例えば、 vector のイテレータのペアを持ち、適切なインターフェースを実装した構造体を作る。
size() ：頂点数。

CSR 形式は、次の $2$ つの配列を持って上の機能を実現します。

長さ $n+1$ 、隣接リストを $n$ 個に分ける位置の情報
長さ $m$ （有向辺の個数）、隣接リスト本体

グラフアルゴリズムのライブラリ（競技でよく用いるアルゴリズムを予め用意したもの）に CSR 形式の構造を追加し、各ライブラリの入力をそれに変更します。

いままで vector<vector<int>> を使っていた場合でも暗黙の型変換によって新しいライブラリを自然に利用できます。さらに、なんとこの場合にも（冗長な変換にもかかわらず）高速化が望めます！！（ https://twitter.com/NachiaVivias/status/1484792651027468293 ）

一般に、 CSR 形式は疎な行列に対して用いられるものですが、グラフの隣接行列に適用すると上で紹介したものになります。

密な行列に対して使うことも考えられますが、検証をしていないので高速化の効果への言及を避けます。

既存の実装例

AtCoder Library の強連結成分分解ライブラリ

インターフェースが add_edge なので私は気持ち悪いような気もしていましたが、内部で CSR 形式を使っていたのですね。

Nyaan's Library

docs : https://nyaannyaan.github.io/library/graph/static-graph.hpp

いかにもそれ用のファイルがあります。また、説明のページでは、キャッシュミスが減ることが高速化の要因であることが述べられています。

効果

貼るだけならおそらく簡単だから各自のライブラリで試してみて