Graph - グラフ構造
(Library/Graph/Graph.hpp)

• View this file on GitHub
• Last update: 2026-02-13 15:23:31+09:00
• Include: #include "Library/Graph/Graph.hpp"

Graph - グラフ構造

無向 / 有向グラフを扱うクラスです。

Function

Constructor

Graph<WeightType>(int V)

• 頂点数 $V$ で辺数 $0$ のグラフを構築します。
• 頂点には $0, 1, \dots, V - 1$ の番号が振られているとします。
• WeightType は辺の重みの型を表します。省略した場合は int32_t となります。

制約

• $0 \le V \le 10^6$

計算量

• $\textrm{O}(V)$

---

AddUndirectedEdge

void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1)

• $2$ 頂点 $u, v$ 間に重み $w$ の無向辺を張ります。
• 重み $w$ は省略することが可能です。省略した場合の重みは $1$ となります。

制約

• $0 \le u, v \lt V$
• $w$ は WeightType 型で表現できる値であること

計算量

• $\textrm{O}(1)$

---

AddDirectedEdge

void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1)

• 頂点 $u$ から頂点 $v$ に重み $w$ の有向辺を張ります。
• 重み $w$ は省略することが可能です。省略した場合は重みは $1$ となります。

制約

• $0 \le u, v \lt V$
• $w$ は WeightType 型で表現できる値であること

計算量

• $\textrm{O}(1)$

---

VertexSize

inline size_t VertexSize() const

• グラフ $G$ の頂点数 $V$ を取得します。

計算量

• $\textrm{O}(1)$

---

EdgeSize

inline size_t EdgeSize() const

• グラフ $G$ の辺数 $E$ を取得します。

計算量

• $\textrm{O}(1)$

---

operator[]

(1) vector<Edge<WeightType>> &operator[](const Vertex v)
(1) const vector<Edge<WeightType>> &operator[](const Vertex v) const

• 頂点 $v$ から出次している辺の一覧を取得します。

(1) for(auto e : G[u])
(2) for(Vertex v : G[u])

• (1) $G$ の頂点 $u$ から出次している辺の一覧(std::vector<Edge<WeightType>>)を取得します。
• (2) $G$ の頂点 $u$ に隣接している頂点 $v$ の一覧(std::vector<Vertex>)を取得します。

制約

• $0 \le v \lt V$

計算量

• $\textrm{O}(1)$

Depends on

• Library/Common.hpp

Required by

• Bellman Ford - ベルマンフォード法 (Library/Graph/BellmanFord.hpp)
• Cycle Detection - 閉路検出 (Library/Graph/CycleDetection.hpp)
• Dijkstra - ダイクストラ法 (Library/Graph/Dijkstra.hpp)
• Graph Utilities - グラフユーティリティ (Library/Graph/GraphMisc.hpp)
• Kruskal - クラスカル法 (Library/Graph/Kruskal.hpp)
• Low Link - 関節点と橋 (Library/Graph/LowLink.hpp)
• Strongly Connected Components - 強連結成分分解 (Library/Graph/StronglyConnectedComponents.hpp)
• Warshall Floyd - ワーシャルフロイド法 (Library/Graph/WarshallFloyd.hpp)
• Trie - トライ木 (Library/String/Trie.hpp)
• Heavy Light Decomposition - 重軽分解 (Library/Tree/HeavyLightDecomposition.hpp)
• Lowest Common Ancestor - 最小共通祖先 (Library/Tree/LowestCommonAncestor.hpp)
• Rerooting DP - 全方位木DP (Library/Tree/RerootingDP.hpp)
• Tree - 木 (Library/Tree/Tree.hpp)
• Tree Diameter - 木の直径 (Library/Tree/TreeDiameter.hpp)
• Library/unauthenticated/AuxiliaryTree.hpp
• Library/unauthenticated/EulerTour.hpp

Verified with

• verify/AOJ-ALDS1-7-A.test.cpp
• verify/AOJ-GRL-1-A.test.cpp
• verify/AOJ-GRL-1-B.test.cpp
• verify/AOJ-GRL-1-C.test.cpp
• verify/AOJ-GRL-3-A.test.cpp
• verify/AOJ-GRL-3-B.test.cpp
• verify/AOJ-GRL-3-C.test.cpp
• verify/AOJ-GRL-4-A.test.cpp
• verify/AOJ-GRL-5-A.test.cpp
• verify/AOJ-GRL-5-B.test.cpp
• verify/AOJ-GRL-5-C.test.cpp
• verify/LC-CycleDetection.test.cpp
• verify/LC-CycleDetectionUndirected.test.cpp
• verify/LC-JumponTree.test.cpp
• verify/LC-LowestCommonAncestor-HLD.test.cpp
• verify/LC-LowestCommonAncestor.test.cpp
• verify/LC-MinimumSpanningTree.test.cpp
• verify/LC-ShortestPath.test.cpp
• verify/LC-StronglyConnectedComponents.test.cpp
• verify/LC-TreeDiameter.test.cpp
• verify/LC-TreePathCompositeSum.test.cpp
• verify/LC-VertexAddPathSum.test.cpp
• verify/LC-VertexAddSubtreeSum.test.cpp
• verify/LC-VertexSetPathComposite.test.cpp

Code

#pragma once

#include "../Common.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}

Back to top page