Compressed Sparse Row (CSR)
(Graph/csr.hpp)

• View this file on GitHub
• Last update: 2025-06-21 08:41:08+09:00
• Include: #include "Graph/csr.hpp"

概要

std::vector<std::vector<T>> を1次元でもって定数倍高速化するためのデータ構造。

関数名など	機能	計算量
csr<T>(int N)	宣言。 $N$ 頂点 のグラフを形成する。	$\text{O} (N)$
void add_edge(int u, T v)	頂点 $u$ から辺 $v$ を追加する。	$\text{O} (1)$
void build()	追加した辺をバケットソートして使える状態にする。	$\text{O} (N + M)$
Node csr[v]	頂点 $v$ から張られている辺を返す。	-
T csr[v][i]	頂点 $v$ から張られているi番目の辺を返す。	$\text{O} (1)$
int csr[v].size()	頂点 $v$ から張られている辺の数を返す。	$\text{O} (1)$

Verified with

• Test/yukicoder/yuki3178.test.cpp

Code

template <class T> struct csr {
    using itr = typename std::vector<T>::iterator;
    struct Node {
        itr st, en;
        itr begin() { return st; }
        itr end() { return en; }
        int size() { return en - st; }
        T operator[](int p){ return st[p]; }
    };
    const int N;
    std::vector<int> start;
    std::vector<T> E;
    std::vector<std::pair<int,T>> edge;
    csr(int n) : N(n), start(n + 1) {}
    void add_edge(int u, T v){
        assert(0 <= u && u < N);
        start[u + 1]++;
        edge.emplace_back(u, v);
    }
    void build(){
        E.resize(edge.size());
        for(int i = 0; i < N; i++) start[i + 1] += start[i];
        auto cnt = start;
        for(auto [u, v] : edge) E[cnt[u]++] = v;
    }
    Node operator[](int p) {
        return Node{E.begin() + start[p], E.begin() + start[p + 1]};
    }
};

#line 1 "Graph/csr.hpp"
template <class T> struct csr {
    using itr = typename std::vector<T>::iterator;
    struct Node {
        itr st, en;
        itr begin() { return st; }
        itr end() { return en; }
        int size() { return en - st; }
        T operator[](int p){ return st[p]; }
    };
    const int N;
    std::vector<int> start;
    std::vector<T> E;
    std::vector<std::pair<int,T>> edge;
    csr(int n) : N(n), start(n + 1) {}
    void add_edge(int u, T v){
        assert(0 <= u && u < N);
        start[u + 1]++;
        edge.emplace_back(u, v);
    }
    void build(){
        E.resize(edge.size());
        for(int i = 0; i < N; i++) start[i + 1] += start[i];
        auto cnt = start;
        for(auto [u, v] : edge) E[cnt[u]++] = v;
    }
    Node operator[](int p) {
        return Node{E.begin() + start[p], E.begin() + start[p + 1]};
    }
};

Back to top page