グラフライブラリ
(C++/graph/Graph.hpp)

• View this file on GitHub
• Last update: 2024-07-08 16:24:06+09:00
• Include: #include "C++/graph/Graph.hpp"

Depends on

• Edge (C++/graph/edge.hpp)

Required by

• 重み付きグラフライブラリ (C++/graph/WeightedGraph.hpp)
• 木の直径 (C++/graph/diameter.hpp)

Verified with

• test/cycledetector.test.cpp
• test/dag_check.test.cpp
• test/dijkstra.test.cpp
• test/lca.test.cpp
• test/scc.test.cpp
• test/scc2.test.cpp
• test/shortestpath.test.cpp
• test/spfa.test.cpp
• test/tree_diameter.test.cpp
• test/warshallfloyd.test.cpp

Code

#pragma once

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

#ifndef TEMPLATE
template <class T, class U> bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; }
#endif
#include "C++/graph/edge.hpp"

template <bool undirected = true> struct graph: std::vector<std::vector<edge>> {
protected:
    int indexed, id;
    std::vector<edge> edges;
public:
    graph(){}
    graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this -> resize(n); }
    void add(int a, int b) {
        a -= indexed, b-= indexed;
        (*this)[a].emplace_back(a, b, id);
        edges.emplace_back(a, b, id++);
        if(undirected) {
            (*this)[b].emplace_back(b, a, --id);
            edges.emplace_back(b, a, id++);
        }
    }
    void input(const int m) {
        for(int i = 0; i < m; ++i) {
            int a, b;
            std::cin >> a >> b;
            add(a, b);
        }
    }
    std::vector<edge> get_edge() const { return edges; }
    std::vector<int> all_dist(const int v) {
        std::vector<int> d(this -> size(), -1);
        std::queue<int> q;
        d[v] = 0;
        q.emplace(v);
        while(q.size()) {
            const int tmp = q.front();
            q.pop();
            for(const auto &el: (*this)[tmp]) {
                if(d[el] != -1) {
                    continue;
                }
                d[el] = d[tmp] + 1;
                q.emplace(el);
            }
        }
        return d;
    }
    int dist(const int u, const int v){ return all_dist(u)[v]; }
    std::vector<int> t_sort() {
        const int n = this -> size();
		std::vector<int> deg(n);
		for(int i = 0; i < n; ++i) {
			for(const auto ed: (*this)[i]) {
				deg[ed]++;
			}
		}
		std::stack<int> sk;
		for(int i = 0; i < n; ++i) {
			if(deg[i] == 0) {
				sk.emplace(i);
			}
		}
		std::vector<int> ord;
		while(sk.size()) {
			const auto tmp = sk.top();
            sk.pop();
			ord.emplace_back(tmp);
			for(const auto ed: (*this)[tmp]) {
				if(--deg[ed] == 0) {
					sk.emplace(ed);
				}
			}
		}
		return ord.size() == size() ? ord : std::vector<int>{};
	}
    std::vector<edge> cycle() {
        const int n = size();
        std::vector<int> used(n);
        std::vector<edge> pre(n), cycle;
        const auto dfs = [&](const auto &f, const int i) -> bool {
            used[i] = 1;
			for(const auto &e: (*this)[i]) {
				if(used[e] == 0) {
					pre[e] = e;
					if(f(f, e)) {
						return true;
					}
				} else if(used[e] == 1) {
					int now = i;
					while(now != e) {
						cycle.emplace_back(pre[now]);
						now = pre[now].src;
					}
					cycle.emplace_back(e);
					return true;
				}
			}
			used[i] = 2;
			return false;
        };
        for(int i = 0; i < n; ++i) {
			if(used[i] == 0 && dfs(dfs, i)) {
				std::reverse(cycle.begin(), cycle.end());
				return cycle;
			}
		}
		return {};
    }
};
typedef std::vector<edge> ve;
typedef std::vector<ve> we;

/**
 * @brief グラフライブラリ
 */

#line 2 "C++/graph/Graph.hpp"

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

#ifndef TEMPLATE
template <class T, class U> bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; }
#endif
#line 2 "C++/graph/edge.hpp"

struct edge {
    int src, to, id;
    long long cost;
    edge(){}
    edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
    operator int() const { return to; }
};

/**
 * @brief Edge
 */
#line 12 "C++/graph/Graph.hpp"
template <bool undirected = true> struct graph: std::vector<std::vector<edge>> {
protected:
    int indexed, id;
    std::vector<edge> edges;
public:
    graph(){}
    graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this -> resize(n); }
    void add(int a, int b) {
        a -= indexed, b-= indexed;
        (*this)[a].emplace_back(a, b, id);
        edges.emplace_back(a, b, id++);
        if(undirected) {
            (*this)[b].emplace_back(b, a, --id);
            edges.emplace_back(b, a, id++);
        }
    }
    void input(const int m) {
        for(int i = 0; i < m; ++i) {
            int a, b;
            std::cin >> a >> b;
            add(a, b);
        }
    }
    std::vector<edge> get_edge() const { return edges; }
    std::vector<int> all_dist(const int v) {
        std::vector<int> d(this -> size(), -1);
        std::queue<int> q;
        d[v] = 0;
        q.emplace(v);
        while(q.size()) {
            const int tmp = q.front();
            q.pop();
            for(const auto &el: (*this)[tmp]) {
                if(d[el] != -1) {
                    continue;
                }
                d[el] = d[tmp] + 1;
                q.emplace(el);
            }
        }
        return d;
    }
    int dist(const int u, const int v){ return all_dist(u)[v]; }
    std::vector<int> t_sort() {
        const int n = this -> size();
		std::vector<int> deg(n);
		for(int i = 0; i < n; ++i) {
			for(const auto ed: (*this)[i]) {
				deg[ed]++;
			}
		}
		std::stack<int> sk;
		for(int i = 0; i < n; ++i) {
			if(deg[i] == 0) {
				sk.emplace(i);
			}
		}
		std::vector<int> ord;
		while(sk.size()) {
			const auto tmp = sk.top();
            sk.pop();
			ord.emplace_back(tmp);
			for(const auto ed: (*this)[tmp]) {
				if(--deg[ed] == 0) {
					sk.emplace(ed);
				}
			}
		}
		return ord.size() == size() ? ord : std::vector<int>{};
	}
    std::vector<edge> cycle() {
        const int n = size();
        std::vector<int> used(n);
        std::vector<edge> pre(n), cycle;
        const auto dfs = [&](const auto &f, const int i) -> bool {
            used[i] = 1;
			for(const auto &e: (*this)[i]) {
				if(used[e] == 0) {
					pre[e] = e;
					if(f(f, e)) {
						return true;
					}
				} else if(used[e] == 1) {
					int now = i;
					while(now != e) {
						cycle.emplace_back(pre[now]);
						now = pre[now].src;
					}
					cycle.emplace_back(e);
					return true;
				}
			}
			used[i] = 2;
			return false;
        };
        for(int i = 0; i < n; ++i) {
			if(used[i] == 0 && dfs(dfs, i)) {
				std::reverse(cycle.begin(), cycle.end());
				return cycle;
			}
		}
		return {};
    }
};
typedef std::vector<edge> ve;
typedef std::vector<ve> we;

/**
 * @brief グラフライブラリ
 */

Back to top page