C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/オイラー路 有向グラフ版 * * verification-helper: IGNORE * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225 */ #include <iostream> #include <string> #include <vector> #include "emthrm/graph/edge.hpp" #include "emthrm/graph/eulerian_trail_in_directed_graph.hpp" int main() { constexpr int SIGMA = 26; while (true) { int n; std::cin >> n; if (n == 0) [[unlikely]] break; std::vector<std::vector<emthrm::Edge<bool>>> graph(SIGMA); while (n--) { std::string word; std::cin >> word; graph[word.front() - 'a'].emplace_back(word.front() - 'a', word.back() - 'a'); } const std::vector<emthrm::Edge<bool>> trail = emthrm::eulerian_trail_in_directed_graph(graph); std::cout << (!trail.empty() && trail.front().src == trail.back().dst ? "OK\n" : "NG\n"); } return 0; }
#line 1 "test/graph/eulerian_trail_in_directed_graph.test.cpp" /* * @title グラフ/オイラー路 有向グラフ版 * * verification-helper: IGNORE * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225 */ #include <iostream> #include <string> #include <vector> #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/eulerian_trail_in_directed_graph.hpp" #include <algorithm> #include <iterator> #include <ranges> #include <utility> #line 9 "include/emthrm/graph/eulerian_trail_in_directed_graph.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 11 "include/emthrm/graph/eulerian_trail_in_directed_graph.hpp" namespace emthrm { template <typename CostType> std::vector<Edge<CostType>> eulerian_trail_in_directed_graph( std::vector<std::vector<Edge<CostType>>> graph, int s = -1) { const int n = graph.size(); int edge_num = 0; std::vector<int> deg(n, 0); for (int i = 0; i < n; ++i) { edge_num += graph[i].size(); deg[i] += graph[i].size(); for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) { --deg[e]; } } if (edge_num == 0) [[unlikely]] return {}; const int not0 = n - std::count(deg.begin(), deg.end(), 0); if (not0 == 0) { if (s == -1) { s = std::distance( graph.begin(), std::find_if_not( graph.begin(), graph.end(), [](const std::vector<Edge<CostType>>& edges) -> bool { return edges.empty(); })); } } else if (not0 == 2) { bool t_exists = false; for (int i = 0; i < n; ++i) { if (deg[i] == 0) continue; if (deg[i] == 1) { if (s == -1) s = i; if (s != i) return {}; } else if (deg[i] == -1) { if (t_exists) return {}; t_exists = true; } else { return {}; } } } else { return {}; } std::vector<Edge<CostType>> res; const auto dfs = [&graph, &res](auto dfs, const int ver) -> void { while (!graph[ver].empty()) { const Edge<CostType> e = graph[ver].back(); graph[ver].pop_back(); dfs(dfs, e.dst); res.emplace_back(e); } }; dfs(dfs, s); if (std::cmp_equal(res.size(), edge_num)) { std::reverse(res.begin(), res.end()); return res; } return {}; } } // namespace emthrm #line 14 "test/graph/eulerian_trail_in_directed_graph.test.cpp" int main() { constexpr int SIGMA = 26; while (true) { int n; std::cin >> n; if (n == 0) [[unlikely]] break; std::vector<std::vector<emthrm::Edge<bool>>> graph(SIGMA); while (n--) { std::string word; std::cin >> word; graph[word.front() - 'a'].emplace_back(word.front() - 'a', word.back() - 'a'); } const std::vector<emthrm::Edge<bool>> trail = emthrm::eulerian_trail_in_directed_graph(graph); std::cout << (!trail.empty() && trail.front().src == trail.back().dst ? "OK\n" : "NG\n"); } return 0; }