C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/道の検出 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/past202112-open/tasks/past202112_g */ #include <algorithm> #include <iostream> #include <vector> #include "emthrm/graph/detect_path.hpp" #include "emthrm/graph/edge.hpp" int main() { int n, q; std::cin >> n >> q; std::vector<std::vector<emthrm::Edge<bool>>> graph(n); while (q--) { int type, u, v; std::cin >> type >> u >> v; --u; --v; if (type == 1) { const auto adj = std::ranges::find(graph[u], v, &emthrm::Edge<bool>::dst); if (adj != graph[u].end()) { graph[u].erase(adj); graph[v].erase( std::ranges::find(graph[v], u, &emthrm::Edge<bool>::dst)); } else { graph[u].emplace_back(u, v); graph[v].emplace_back(v, u); } } else if (type == 2) { std::cout << (emthrm::detect_path(graph, u, v).empty() ? "No\n" : "Yes\n"); } } return 0; }
#line 1 "test/graph/detect_path.test.cpp" /* * @title グラフ/道の検出 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/past202112-open/tasks/past202112_g */ #include <algorithm> #include <iostream> #include <vector> #line 1 "include/emthrm/graph/detect_path.hpp" #line 5 "include/emthrm/graph/detect_path.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 7 "include/emthrm/graph/detect_path.hpp" namespace emthrm { template <typename CostType> std::vector<Edge<CostType>> detect_path( const std::vector<std::vector<Edge<CostType>>>& graph, const int s, const int t) { std::vector<bool> is_visited(graph.size(), false); std::vector<Edge<CostType>> path; const auto dfs = [&graph, t, &is_visited, &path](auto dfs, const int ver) -> bool { if (ver == t) return true; is_visited[ver] = true; for (const Edge<CostType>& e : graph[ver]) { if (!is_visited[e.dst]) { path.emplace_back(e); if (dfs(dfs, e.dst)) return true; path.pop_back(); } } return false; }; dfs(dfs, s); return path; } } // namespace emthrm #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 14 "test/graph/detect_path.test.cpp" int main() { int n, q; std::cin >> n >> q; std::vector<std::vector<emthrm::Edge<bool>>> graph(n); while (q--) { int type, u, v; std::cin >> type >> u >> v; --u; --v; if (type == 1) { const auto adj = std::ranges::find(graph[u], v, &emthrm::Edge<bool>::dst); if (adj != graph[u].end()) { graph[u].erase(adj); graph[v].erase( std::ranges::find(graph[v], u, &emthrm::Edge<bool>::dst)); } else { graph[u].emplace_back(u, v); graph[v].emplace_back(v, u); } } else if (type == 2) { std::cout << (emthrm::detect_path(graph, u, v).empty() ? "No\n" : "Yes\n"); } } return 0; }