lib/internal/internal_csr.hpp

• View this file on GitHub
• Last update: 2025-05-22 19:33:15+09:00
• Include: #include "lib/internal/internal_csr.hpp"

Required by

• 最小費用流 (lib/flow/min_cost_flow.hpp)
• functional graph (lib/graph/functional_graph.hpp)
• 強連結成分分解 (lib/graph/scc.hpp)
• 2-SAT (lib/graph/two_sat.hpp)
• lib/tree/auxiliary_tree.hpp
• HL分解 (lib/tree/hld.hpp)
• lib/tree/linear_lca.hpp

Verified with

• test/aoj/challenge/2270.test.cpp
• test/aoj/grl/hld.test.cpp
• test/aoj/grl/min_cost_flow.test.cpp
• test/aoj/grl/range_query_on_tree.test.cpp
• test/aoj/grl/range_query_on_tree_2.test.cpp
• test/aoj/grl/scc.test.cpp
• test/aoj/jag/functional_graph.test.cpp
• test/yosupo/graph/strongly_connected_components.test.cpp
• test/yosupo/other/two_sat.test.cpp
• test/yosupo/tree/jump_on_tree.test.cpp
• test/yosupo/tree/lowest_common_ancestor.2.test.cpp
• test/yosupo/tree/lowest_common_ancestor.test.cpp
• test/yosupo/tree/vertex_add_path_sum.test.cpp
• test/yukicoder/0901.test.cpp
• test/yukicoder/1211.test.cpp
• test/yukicoder/1242.test.cpp

Code

#pragma once
#include <iostream>
#include <utility>
#include <vector>

namespace internal {

struct graph_csr {
  private:
    struct edge_list {
        using const_iterator = std::vector<int>::const_iterator;

        edge_list(const graph_csr &g, int v) : g(g), v(v) {}

        const_iterator begin() const { return std::next(g.elist.begin(), g.start[v]); }
        const_iterator end() const { return std::next(g.elist.begin(), g.start[v + 1]); }

      private:
        const graph_csr &g;
        int v;
    };

  public:
    graph_csr(int n) : _size(n), edges(), start(n + 1) {}

    edge_list operator[](int i) const { return edge_list(*this, i); }

    constexpr int size() const { return _size; }

    void build() {
        for (auto [u, v] : edges) ++start[u + 1];
        for (int i = 0; i < _size; ++i) start[i + 1] += start[i];
        auto counter = start;
        elist = std::vector<int>(edges.size());
        for (auto [u, v] : edges) elist[counter[u]++] = v;
    }

    void add_edge(int u, int v) { edges.emplace_back(u, v); }

    void add_edges(int u, int v) {
        edges.emplace_back(u, v);
        edges.emplace_back(v, u);
    }

    void input_edge(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edge(from - base, to - base);
        }
        build();
    }

    void input_edges(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edges(from - base, to - base);
        }
        build();
    }

    int _size;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> elist;
    std::vector<int> start;
};

template <class E>
struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>> &edges) : start(n + 1), elist(edges.size()) {
        for (auto e : edges) ++start[e.first + 1];
        for (int i = 1; i <= n; ++i) start[i] += start[i - 1];
        auto counter = start;
        for (auto e : edges) elist[counter[e.first]++] = e.second;
    }
};

}  // namespace internal

#line 2 "lib/internal/internal_csr.hpp"
#include <iostream>
#include <utility>
#include <vector>

namespace internal {

struct graph_csr {
  private:
    struct edge_list {
        using const_iterator = std::vector<int>::const_iterator;

        edge_list(const graph_csr &g, int v) : g(g), v(v) {}

        const_iterator begin() const { return std::next(g.elist.begin(), g.start[v]); }
        const_iterator end() const { return std::next(g.elist.begin(), g.start[v + 1]); }

      private:
        const graph_csr &g;
        int v;
    };

  public:
    graph_csr(int n) : _size(n), edges(), start(n + 1) {}

    edge_list operator[](int i) const { return edge_list(*this, i); }

    constexpr int size() const { return _size; }

    void build() {
        for (auto [u, v] : edges) ++start[u + 1];
        for (int i = 0; i < _size; ++i) start[i + 1] += start[i];
        auto counter = start;
        elist = std::vector<int>(edges.size());
        for (auto [u, v] : edges) elist[counter[u]++] = v;
    }

    void add_edge(int u, int v) { edges.emplace_back(u, v); }

    void add_edges(int u, int v) {
        edges.emplace_back(u, v);
        edges.emplace_back(v, u);
    }

    void input_edge(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edge(from - base, to - base);
        }
        build();
    }

    void input_edges(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edges(from - base, to - base);
        }
        build();
    }

    int _size;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> elist;
    std::vector<int> start;
};

template <class E>
struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>> &edges) : start(n + 1), elist(edges.size()) {
        for (auto e : edges) ++start[e.first + 1];
        for (int i = 1; i <= n; ++i) start[i] += start[i - 1];
        auto counter = start;
        for (auto e : edges) elist[counter[e.first]++] = e.second;
    }
};

}  // namespace internal

Back to top page