Graph2/GraphTemplate.hpp

• View this file on GitHub
• Last update: 2023-07-17 18:02:31+09:00
• Include: #include "Graph2/GraphTemplate.hpp"
• Link: https://ei1333.github.io/library/graph/graph-template.hpp

Required by

• Graph2/CycleDetection.hpp
• Dijkstra (Graph2/Dijkstra.hpp)
• Graph2/DoublingLowestCommonAncestor.hpp
• Eppstein's Algorithm (K-Shortest-Walk) (Graph2/Eppstein.hpp)
• Graph2/GraphRelabel.hpp
• Heavy Light Decomposition (HL分解) (Graph2/HeavyLightDecomposition.hpp)
• Low Link (Graph2/LowLink.hpp)
• 区間に辺を張るテク (Graph2/RangeEdgeGraph.hpp)
• Graph2/Rerooting.hpp
• Strongly Connected Components (Graph2/StronglyConnectedComponents.hpp)
• Graph2/TreeDiameter.hpp
• Graph2/TwoEdgeConnectedComponents.hpp
• Graph2/WeightedMaximumIndependentSet.hpp
• Yen's Algorithm (K-Shortest-Path) (Graph2/Yen.hpp)

Verified with

• test/AOJ_GRL_1_A.test.cpp
• test/AOJ_GRL_3_A.test.cpp
• test/yosupo_CycleDetection2.test.cpp
• test/yosupo_KSW.test.cpp
• test/yosupo_TECC.test.cpp
• test/yosupo_TreeDiameter.test.cpp
• test/yosupo_scc2.test.cpp
• test/yuki1249.test.cpp
• test/yuki4227.test.cpp
• test/yuki5436.test.cpp

Code

#ifndef GRAPH_TEMPLATE_
#define GRAPH_TEMPLATE_

// graph template
// ref : https://ei1333.github.io/library/graph/graph-template.hpp
template<typename T=int>
struct Edge{
    int from,to;
    T w;
    int idx;
    Edge()=default;
    Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}
    operator int() const{return to;}
};

template<typename T=int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int V,E;
    Graph()=default;
    Graph(int n):g(n),V(n),E(0){}

    int size(){
        return (int)g.size();
    }
    void resize(int k){
        g.resize(k);
        V=k;
    }
    inline const vector<Edge<T>> &operator[](int k)const{
        return (g.at(k));
    }
    inline vector<Edge<T>> &operator[](int k){
        return (g.at(k));
    }
    void add_directed_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E++);
    }
    void add_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E);
        g[to].emplace_back(to,from,cost,E++);
    }
    void read(int m,int pad=-1,bool weighted=false,bool directed=false){
        for(int i=0;i<m;i++){
            int u,v;cin>>u>>v;
            u+=pad,v+=pad;
            T w=T(1);
            if(weighted) cin>>w;
            if(directed) add_directed_edge(u,v,w);
            else         add_edge(u,v,w);
        }
    }
};

#endif /* GRAPH_TEMPLATE_ */

#line 1 "Graph2/GraphTemplate.hpp"



// graph template
// ref : https://ei1333.github.io/library/graph/graph-template.hpp
template<typename T=int>
struct Edge{
    int from,to;
    T w;
    int idx;
    Edge()=default;
    Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}
    operator int() const{return to;}
};

template<typename T=int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int V,E;
    Graph()=default;
    Graph(int n):g(n),V(n),E(0){}

    int size(){
        return (int)g.size();
    }
    void resize(int k){
        g.resize(k);
        V=k;
    }
    inline const vector<Edge<T>> &operator[](int k)const{
        return (g.at(k));
    }
    inline vector<Edge<T>> &operator[](int k){
        return (g.at(k));
    }
    void add_directed_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E++);
    }
    void add_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E);
        g[to].emplace_back(to,from,cost,E++);
    }
    void read(int m,int pad=-1,bool weighted=false,bool directed=false){
        for(int i=0;i<m;i++){
            int u,v;cin>>u>>v;
            u+=pad,v+=pad;
            T w=T(1);
            if(weighted) cin>>w;
            if(directed) add_directed_edge(u,v,w);
            else         add_edge(u,v,w);
        }
    }
};

Back to top page