グラフビルダー (daylight/graph/builder.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/graph/builder.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)
• daylight/graph/base.hpp

Verified with

• test/aoj/grl/1_A.test.cpp
• test/aoj/grl/1_C.test.cpp
• test/aoj/grl/2_A.test.cpp
• test/yosupo/tree/jump_on_tree.test.cpp
• test/yosupo/tree/lca.test.cpp
• test/yosupo/tree/tree_diameter.test.cpp

Code

#pragma once
#include "daylight/base.hpp"
#include "daylight/graph/base.hpp"

/// @brief グラフビルダー
template<typename T = ll>
class GraphBuilder {
private:
	int N, M;
	Graph<T> G;
	int index = 1;
	bool m_weighted = false;
	bool m_directed = false;
	bool m_tree_format = false;

public:
	GraphBuilder(int N): N(N), M(N - 1) {
		G = Graph<T>(N);
	}

	GraphBuilder(int N, int M): N(N), M(M) {
		G = Graph<T>(N);
	}

	GraphBuilder& setIndex(int index = 1) {
		this->index = index;
		return *this;
	}

	GraphBuilder& weighted(bool weighted = true) {
		this->m_weighted = weighted;
		return *this;
	}

	GraphBuilder& directed(bool directed = true) {
		this->m_directed = directed;
		return *this;
	}

	GraphBuilder& useTreeFormat(bool tree_format = true) {
		this->m_tree_format = tree_format;
		return *this;
	}

	Graph<T> build(istream& in) {
		if(this->m_tree_format) {
			FOR(i, 1, N) {
				int p;
				cin >> p;
				p -= index;
				T c(1);
				if(m_weighted) {
					in >> c;
				}
				G[p].eb(p, i, c);
				if(!m_directed) {
					G[i].eb(i, p, c);
				}
			}
		} else {
			REP(i, M) {
				int u, v;
				in >> u >> v;
				u -= index;
				v -= index;
				T c(1);
				if(m_weighted) {
					in >> c;
				}
				G[u].eb(u, v, c);
				if(!m_directed) {
					G[v].eb(v, u, c);
				}
			}
		}
		return G;
	}

	vector<vector<T>> buildMatrix(istream& in,
								  T non_edge = LINF) {
		vector<vector<T>> G(N, vector<T>(N, non_edge));
		if(this->m_tree_format) {
			FOR(i, 1, N) {
				int p;
				cin >> p;
				p -= index;
				T c(1);
				if(m_weighted) {
					in >> c;
				}
				G[p][i] = c;
				if(!m_directed) {
					G[i][p] = c;
				}
			}
		} else {
			REP(i, M) {
				int u, v;
				in >> u >> v;
				u -= index;
				v -= index;
				T c(1);
				if(m_weighted) {
					in >> c;
				}
				G[u][v] = c;
				if(!m_directed) {
					G[v][u] = c;
				}
			}
		}
		return G;
	}

	Edges<T> buildEdgeList(istream& in) {
		Edges<T> edges;
		if(this->m_tree_format) {
			FOR(i, 1, N) {
				int p;
				cin >> p;
				p -= index;
				T c(1);
				if(m_weighted) {
					in >> c;
				}
				edges.eb(p, i, c);
				if(!m_directed) {
					edges.eb(i, p, c);
				}
			}
		} else {
			REP(i, M) {
				int u, v;
				in >> u >> v;
				u -= index;
				v -= index;
				T c(1);
				if(m_weighted) {
					in >> c;
				}
				edges.eb(u, v, c);
				if(!m_directed) {
					edges.eb(v, u, c);
				}
			}
		}
		return edges;
	}
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page