Test/Graph/Normal/StronglyConnectedComponents.test.cpp

View this file on GitHub
Last update: 2025-07-06 21:41:14+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C"

// begin:tag includes

#include "../../../Library/Graph/Normal/StronglyConnectedComponents.hpp"


#include "../../../Library/Graph/Graph.hpp"

#include "../../../Library/Range/istream.hpp"

// end:tag includes


signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  auto [n, m] = mtd::io::in<int, int>();
  auto graph = mtd::Graph(n);
  for (auto [f, t] : mtd::views::istream<int, int>(m)) { graph.addArc(f, t); }

  auto scc = mtd::StronglyConnectedComponents(std::move(graph));

  auto [q] = mtd::io::in<int>();
  for (auto [u, v] : mtd::views::istream<int, int>(q)) {
    std::cout << scc.isSameGroup(u, v) << std::endl;
  }
}

#line 1 "Test/Graph/Normal/StronglyConnectedComponents.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C"

// begin:tag includes

#line 2 "Library/Graph/Normal/StronglyConnectedComponents.hpp"

#include <algorithm>

#include <concepts>

#include <ranges>

#include <set>

#include <unordered_set>

#include <vector>


#line 2 "Library/Graph/Graph.hpp"
#include <deque>

#include <iostream>

#line 5 "Library/Graph/Graph.hpp"
#include <tuple>

#line 7 "Library/Graph/Graph.hpp"

namespace mtd {
  template <class Node = long long, class Cost = long long>
  class Graph {
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

  public:
    Graph(int n) : m_n(n), m_graph(n) {}
    Graph(const std::vector<Edges>& edges)
        : m_n(edges.size()), m_graph(edges) {}
    Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v);
        } else {
          addEdge(u, v);
        }
      }
    }
    Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v, c] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v, c);
        } else {
          addEdge(u, v, c);
        }
      }
    }

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
      addArc(f, t, c);
      addArc(t, f, c);
    }
    auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
      m_graph[f].emplace_back(t, c);
    }
    auto getEdges(const Node& from) const {
      class EdgesRange {
        const typename Edges::const_iterator b, e;

      public:
        EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
        auto begin() const { return b; }
        auto end() const { return e; }
      };
      return EdgesRange(m_graph[from]);
    }
    auto getEdges() const {
      std::deque<std::tuple<Node, Node, Cost>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, c] : getEdges(from)) {
          edges.emplace_back(from, to, c);
        }
      }
      return edges;
    }
    auto getEdgesExcludeCost() const {
      std::deque<std::pair<Node, Node>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, _] : getEdges(from)) {
          edges.emplace_back(from, to);
        }
      }
      return edges;
    }
    auto reverse() const {
      auto rev = Graph<Node, Cost>(m_n);
      for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
      return rev;
    }
    auto size() const { return m_n; };
    auto debug(bool directed = false) const {
      for (const auto& [f, t, c] : getEdges()) {
        if (f < t || directed) {
          std::cout << f << " -> " << t << ": " << c << std::endl;
        }
      }
    }
  };
}  // namespace mtd

#line 11 "Library/Graph/Normal/StronglyConnectedComponents.hpp"

namespace mtd {
  template <class Node, class Cost>
  class StronglyConnectedComponents {
    struct HashPair {
      template <class T1, class T2>
      size_t operator()(const std::pair<T1, T2>& p) const {
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        size_t seed = 0;
        seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
      }
    };

    const Graph<Node, Cost> m_graph;
    const std::vector<Node> m_group;

    template <class F>
    constexpr static inline auto dfs(const Graph<Node, Cost>& graph, Node from,
                                     std::vector<bool>& is_used, const F& f)
        -> void {
      is_used[from] = true;
      for (const auto& [to, _] : graph.getEdges(from)) {
        if (is_used[to]) { continue; }
        dfs(graph, to, is_used, f);
      }
      f(from);
    }

    constexpr static auto constructGroup(const Graph<Node, Cost>& graph) {
      int n = graph.size();
      std::vector<Node> order;
      std::vector<bool> is_used(n);
      for (auto from : std::views::iota(0, n)) {
        if (is_used[from]) { continue; }
        dfs(graph, from, is_used, [&](auto f) { order.emplace_back(f); });
      }

      int g = 0;
      std::vector<Node> group(n);
      std::vector<bool> is_used2(n);
      auto rev = graph.reverse();
      for (auto from : order | std::views::reverse) {
        if (is_used2[from]) { continue; }
        dfs(rev, from, is_used2, [&](auto f) { group[f] = g; });
        ++g;
      }
      return group;
    }

  public:
    [[deprecated]] constexpr StronglyConnectedComponents(
        const Graph<Node, Cost>& graph)
        : m_graph(graph), m_group(constructGroup(m_graph)) {}
    // graphのコピーコストが大きいのでこっち推奨

    constexpr StronglyConnectedComponents(Graph<Node, Cost>&& graph)
        : m_graph(std::move(graph)), m_group(constructGroup(m_graph)) {}

    constexpr auto size() const {
      return *std::max_element(m_group.begin(), m_group.end()) + 1;
    }
    constexpr auto group(Node a) const { return m_group[a]; }
    constexpr auto isSameGroup(Node a, Node b) const {
      return m_group[a] == m_group[b];
    }
    constexpr auto getGroupNodes() const {
      std::vector<std::vector<Node>> groupNodes(size());
      for (int gi = 0; gi < m_graph.size(); ++gi) {
        groupNodes[m_group[gi]].emplace_back(gi);
      }
      return groupNodes;
    }
    constexpr auto getGroupGraph() const {
      std::unordered_set<std::pair<Node, Node>, HashPair> st;
      st.reserve(m_graph.size());
      for (int f = 0; f < m_graph.size(); ++f) {
        for (const auto& [t, _] : m_graph.getEdges(f)) {
          if (!isSameGroup(f, t)) { st.emplace(m_group[f], m_group[t]); }
        }
      }
      Graph<Node, Cost> ret(size());
      for (const auto& [f, t] : st) { ret.addArc(f, t); }
      return ret;
    }
  };
}  // namespace mtd

#line 5 "Test/Graph/Normal/StronglyConnectedComponents.test.cpp"

#line 2 "Library/Range/istream.hpp"

#line 4 "Library/Range/istream.hpp"

#line 2 "Library/Utility/io.hpp"

#line 5 "Library/Utility/io.hpp"
#include <type_traits>
#line 7 "Library/Utility/io.hpp"

#line 2 "Library/Utility/Tuple.hpp"

#include <functional>

namespace mtd {
  namespace util {
    template <class F, class T>
    constexpr auto tuple_transform(F&& f, T&& t) {
      return std::apply(
          [&]<class... Ts>(Ts&&... elems) {
            return std::tuple<std::invoke_result_t<F&, Ts>...>(
                std::invoke(f, std::forward<Ts>(elems))...);
          },
          std::forward<T>(t));
    }
    template <class F, class T>
    constexpr auto tuple_for_each(F&& f, T&& t) {
      std::apply(
          [&]<class... Ts>(Ts&&... elems) {
            (std::invoke(f, std::forward<Ts>(elems)), ...);
          },
          std::forward<T>(t));
    }
  }  // namespace util
}  // namespace mtd
#line 9 "Library/Utility/io.hpp"

namespace mtd {
  namespace io {

    namespace __details {
      template <typename T>
      concept is_vec = std::same_as<
          T, std::vector<typename T::value_type, typename T::allocator_type>>;
      template <typename T>
      concept is_mat = is_vec<T> && is_vec<typename T::value_type>;

    }  // namespace __details

    template <class T>
    constexpr auto _input() {
      T x;
      std::cin >> x;
      return x;
    }
    template <typename T>
    requires requires { typename std::tuple_size<T>::type; }
    constexpr auto _input() {
      T x;
      util::tuple_for_each([](auto&& i) { std::cin >> i; }, x);
      return x;
    }
    template <__details::is_vec T>
    constexpr auto _input(int n) {
      std::vector<typename T::value_type> v;
      v.reserve(n);
      for (auto i : std::views::iota(0, n)) {
        v.emplace_back(_input<typename T::value_type>());
      }
      return v;
    }
    template <__details::is_mat T>
    constexpr auto _input(int h, int w) {
      T mat;
      mat.reserve(h);
      for (auto i : std::views::iota(0, h)) {
        mat.emplace_back(_input<typename T::value_type>(w));
      }
      return mat;
    }

    template <int N, class Tuple, class T, class... Args, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Sizes... sizes);
    template <int N, class Tuple, __details::is_vec T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size, Sizes... sizes);
    template <int N, class Tuple, __details::is_mat T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size_h, Size size_w,
                                Sizes... sizes);

    template <int N, class Tuple, class T, class... Args, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Sizes... sizes) {
      std::get<N>(t) = _input<T>();
      if constexpr (sizeof...(Args) > 0) {
        _tuple_input<N + 1, Tuple, Args...>(t, sizes...);
      }
    }
    template <int N, class Tuple, __details::is_vec T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size, Sizes... sizes) {
      std::get<N>(t) = _input<T>(size);
      if constexpr (sizeof...(Args) > 0) {
        _tuple_input<N + 1, Tuple, Args...>(t, sizes...);
      }
    }
    template <int N, class Tuple, __details::is_mat T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size_h, Size size_w,
                                Sizes... sizes) {
      std::get<N>(t) = _input<T>(size_h, size_w);
      if constexpr (sizeof...(Args) > 0) {
        _tuple_input<N + 1, Tuple, Args...>(t, sizes...);
      }
    }

    template <class... Args, class... Sizes>
    requires(std::convertible_to<Sizes, size_t>&&...) constexpr auto in(
        Sizes... sizes) {
      auto base = std::tuple<Args...>();
      _tuple_input<0, decltype(base), Args...>(base, sizes...);
      return base;
    }

  }  // namespace io

}  // namespace mtd
#line 6 "Library/Range/istream.hpp"

namespace mtd {
  namespace ranges {

    constexpr int _inf = 1e9;

    template <class... Args>
    struct istream_view
        : public std::ranges::view_interface<istream_view<Args...>> {
      class iterator {
        int count;
        std::tuple<Args...> val;

      public:
        using difference_type = int;
        using value_type = decltype(val);
        using iterator_concept = std::input_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _count) : count(_count) {
          operator++();
        }

        constexpr auto operator*() const { return val; }
        constexpr auto& operator++() {
          --count;
          if (count >= 0) { val = io::in<Args...>(); }
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }

        constexpr auto operator==(const iterator& s) const {
          return count == s.count;
        }
        constexpr auto operator==(std::default_sentinel_t) const {
          return count < 0 || std::cin.eof() || std::cin.fail() ||
                 std::cin.bad();
        }
        constexpr friend auto operator==(std::default_sentinel_t s,
                                         const iterator& li) {
          return li == s;
        }
      };

      int count;

    public:
      constexpr explicit istream_view(int _count) : count(_count) {}
      constexpr explicit istream_view() : istream_view(_inf) {}
      constexpr auto begin() const { return iterator(count); }
      constexpr auto end() const { return std::default_sentinel; }
    };
  }  // namespace ranges

  namespace views {
    namespace __detail {
      template <typename... _Args>
      concept __can_istream_view = requires {
        ranges::istream_view(std::declval<_Args>()...);
      };
    }  // namespace __detail

    template <class... Args>
    struct _Istream {
      template <class... _Tp>
      requires __detail::__can_istream_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const {
        return ranges::istream_view<Args...>(std::forward<_Tp>(__e)...);
      }
    };

    template <class... Args>
    inline constexpr _Istream<Args...> istream{};
  }  // namespace views

}  // namespace mtd
#line 8 "Test/Graph/Normal/StronglyConnectedComponents.test.cpp"
// end:tag includes


signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  auto [n, m] = mtd::io::in<int, int>();
  auto graph = mtd::Graph(n);
  for (auto [f, t] : mtd::views::istream<int, int>(m)) { graph.addArc(f, t); }

  auto scc = mtd::StronglyConnectedComponents(std::move(graph));

  auto [q] = mtd::io::in<int>();
  for (auto [u, v] : mtd::views::istream<int, int>(q)) {
    std::cout << scc.isSameGroup(u, v) << std::endl;
  }
}