グラフ/道の検出
(test/graph/detect_path.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://atcoder.jp/contests/past202112-open/tasks/past202112_g

Depends on

• 道 (path) の検出 (include/emthrm/graph/detect_path.hpp)
• 辺 (include/emthrm/graph/edge.hpp)

Code

/*
 * @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;
}

Back to top page