proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:warning: tests/scc_graph/edges_to_scc.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc204/tasks/abc204_c
// competitive-verifier: IGNORE

#include <iostream>
#include "tools/scc_graph.hpp"
#include "tools/dynamic_bitset.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, M;
  std::cin >> N >> M;
  tools::scc_graph graph(N);
  for (ll i = 0; i < M; ++i) {
    ll A, B;
    std::cin >> A >> B;
    --A, --B;
    graph.add_edge(A, B);
  }

  graph.build();

  std::vector<tools::dynamic_bitset> dp(graph.sccs().size(), tools::dynamic_bitset(N));
  for (ll i = graph.sccs().size() - 1; i >= 0; --i) {
    for (const auto v : graph.sccs()[i]) {
      dp[i].set(v);
    }
    for (const auto& [j, unused] : graph.edges_to_scc(i)) {
      dp[j] |= dp[i];
    }
  }

  ll answer = 0;
  for (ll i = 0; i < N; ++i) {
    answer += dp[graph.scc_id(i)].count();
  }
  std::cout << answer << '\n';
  return 0;
}

#line 1 "tests/scc_graph/edges_to_scc.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc204/tasks/abc204_c
// competitive-verifier: IGNORE

#include <iostream>
#line 1 "tools/scc_graph.hpp"



#include <vector>
#include <utility>
#include <cstddef>
#include <cassert>
#include <stack>
#include <algorithm>
#line 1 "tools/less_by.hpp"



namespace tools {

  template <class F>
  class less_by {
  private:
    F selector;

  public:
    less_by(const F& selector) : selector(selector) {
    }

    template <class T>
    bool operator()(const T& x, const T& y) const {
      return selector(x) < selector(y);
    }
  };
}


#line 11 "tools/scc_graph.hpp"

namespace tools {
  class scc_graph {
  private:
    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;
    ::std::vector<::std::vector<::std::size_t>> m_rev_graph;
    ::std::vector<::std::size_t> m_vid2scc;
    ::std::vector<::std::vector<::std::size_t>> m_sccs;
    ::std::vector<::std::vector<::std::size_t>> m_edges_in_scc;
    ::std::vector<::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>> m_scc_graph;
    ::std::vector<::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>> m_rev_scc_graph;
    bool m_built;

  public:
    scc_graph() = default;
    scc_graph(const ::tools::scc_graph&) = default;
    scc_graph(::tools::scc_graph&&) = default;
    ~scc_graph() = default;
    ::tools::scc_graph& operator=(const ::tools::scc_graph&) = default;
    ::tools::scc_graph& operator=(::tools::scc_graph&&) = default;

    explicit scc_graph(const ::std::size_t n) : m_graph(n), m_rev_graph(n), m_vid2scc(n), m_built(false) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(const ::std::size_t from, const ::std::size_t to) {
      assert(from < this->size());
      assert(to < this->size());
      assert(!this->m_built);
      const auto edge_id = this->m_edges.size();
      this->m_edges.emplace_back(from, to);
      this->m_graph[from].push_back(edge_id);
      this->m_rev_graph[to].push_back(edge_id);
      return edge_id;
    }

    ::std::pair<::std::size_t, ::std::size_t> edge(const ::std::size_t i) const {
      assert(i < this->m_edges.size());
      return this->m_edges[i];
    }
    const ::std::vector<::std::size_t>& edges_from(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_graph[i];
    }
    const ::std::vector<::std::size_t>& edges_to(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_rev_graph[i];
    }

    void build() {
      assert(!this->m_built);
      ::std::stack<::std::size_t> ordered_by_dfs;
      {
        ::std::vector<bool> visited(this->size(), false);
        ::std::stack<::std::pair<bool, ::std::size_t>> stack;
        for (::std::size_t i = this->size(); i --> 0;) {
          stack.emplace(true, i);
        }
        while (!stack.empty()) {
          const auto [pre, here] = stack.top();
          stack.pop();
          if (pre) {
            if (visited[here]) continue;
            visited[here] = true;
            stack.emplace(false, here);
            for (const auto e : this->m_graph[here]) {
              const auto next = this->m_edges[e].second;
              if (visited[next]) continue;
              stack.emplace(true, next);
            }
          } else {
            ordered_by_dfs.push(here);
          }
        }
      }

      {
        ::std::vector<bool> visited(this->size(), false);
        while (!ordered_by_dfs.empty()) {
          const auto root = ordered_by_dfs.top();
          ordered_by_dfs.pop();
          if (visited[root]) continue;

          const auto scc_id = this->m_sccs.size();
          this->m_sccs.emplace_back();
          this->m_edges_in_scc.emplace_back();
          this->m_scc_graph.emplace_back();
          this->m_rev_scc_graph.emplace_back();

          ::std::stack<::std::size_t> stack({root});
          while (!stack.empty()) {
            const auto here = stack.top();
            stack.pop();
            if (visited[here]) continue;
            visited[here] = true;

            this->m_vid2scc[here] = scc_id;
            this->m_sccs[scc_id].push_back(here);

            for (const auto e : this->m_rev_graph[here]) {
              const auto next = this->m_edges[e].first;
              if (visited[next]) continue;
              stack.push(next);
            }
          }

          ::std::vector<::std::size_t> buffer; 
          for (const auto v : this->m_sccs[scc_id]) {
            for (const auto e : this->m_rev_graph[v]) {
              const auto u = this->m_edges[e].first;
              if (this->m_vid2scc[u] == this->m_vid2scc[v]) {
                this->m_edges_in_scc[scc_id].push_back(e);
              } else {
                buffer.push_back(e);
              }
            }
          }

          ::std::sort(buffer.begin(), buffer.end(), tools::less_by([&](const auto e) { return this->m_vid2scc[this->m_edges[e].first]; }));
          for (::std::size_t l = 0, r = 0; l < buffer.size(); l = r) {
            const auto u_scc_id = this->m_vid2scc[this->m_edges[buffer[l]].first];
            this->m_rev_scc_graph[scc_id].emplace_back(u_scc_id, ::std::vector<::std::size_t>());
            for (; r < buffer.size() && this->m_vid2scc[this->m_edges[buffer[l]].first] == this->m_vid2scc[this->m_edges[buffer[r]].first]; ++r);
            for (::std::size_t i = l; i < r; ++i) {
              this->m_rev_scc_graph[scc_id].back().second.push_back(buffer[i]);
            }
          }
        }

        for (::std::size_t v_scc_id = 0; v_scc_id < this->m_sccs.size(); ++v_scc_id) {
          for (const auto& [u_scc_id, edge_ids] : this->m_rev_scc_graph[v_scc_id]) {
            this->m_scc_graph[u_scc_id].emplace_back(v_scc_id, edge_ids);
          }
        }
      }

      this->m_built = true;
    }

    ::std::size_t scc_id(const ::std::size_t i) const {
      assert(i < this->size());
      assert(this->m_built);
      return this->m_vid2scc[i];
    }
    const ::std::vector<::std::vector<::std::size_t>>& sccs() const {
      assert(this->m_built);
      return this->m_sccs;
    }
    const ::std::vector<::std::size_t>& edges_in_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_edges_in_scc[i];
    }
    const ::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>& edges_from_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_scc_graph[i];
    }
    const ::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>& edges_to_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_rev_scc_graph[i];
    }
  };
}


#line 1 "tools/dynamic_bitset.hpp"



#line 5 "tools/dynamic_bitset.hpp"
#include <bit>
#line 8 "tools/dynamic_bitset.hpp"
#include <cstdint>
#line 10 "tools/dynamic_bitset.hpp"
#include <iterator>
#include <limits>
#include <sstream>
#include <string>
#line 1 "tools/ceil.hpp"



#line 5 "tools/ceil.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 16 "tools/dynamic_bitset.hpp"

namespace tools {
  class dynamic_bitset {
    constexpr static ::std::size_t W = ::std::numeric_limits<::std::uint64_t>::digits;
    ::std::size_t m_size;
    ::std::vector<::std::uint64_t> m_bits;

  public:
    class reference {
      friend class ::tools::dynamic_bitset;

      ::tools::dynamic_bitset *m_parent;
      ::std::size_t m_pos;

      reference(::tools::dynamic_bitset * const parent, const ::std::size_t pos) : m_parent(parent), m_pos(pos) {
      }

    public:
      reference(const reference&) = default;
      reference& operator=(const bool x) {
        this->m_parent->set(this->m_pos, x);
        return *this;
      }
      reference& operator=(const reference& other) {
        return *this = static_cast<bool>(other);
      }
      bool operator~() const {
        return !static_cast<bool>(*this);
      }
      operator bool() const {
        return this->m_parent->test(this->m_pos);
      }
      reference& flip() {
        this->m_parent->flip(this->m_pos);
        return *this;
      }
    };

    dynamic_bitset() : m_size(0) {}
    explicit dynamic_bitset(const ::std::size_t size) : m_size(size), m_bits(::tools::ceil(size, W), 0) {}
    explicit dynamic_bitset(const ::std::string& str) : m_size(str.size()), m_bits(::tools::ceil(str.size(), W), 0) {
      for (::std::size_t i = 0; i < str.size(); ++i) {
        const auto c = str[str.size() - 1 - i];
        assert(c == '0' || c == '1');
        if (c == '1') {
          this->m_bits[i / W] |= UINT64_C(1) << (i % W);
        }
      }
    }

    ::tools::dynamic_bitset& operator&=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] &= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator|=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] |= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator^=(const ::tools::dynamic_bitset& other) {
      assert(this->m_size == other.m_size);
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] ^= other.m_bits[i];
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator<<=(const ::std::size_t pos) {
      const ::std::size_t diff = pos / W;
      if (diff < this->m_bits.size()) {
        if (pos % W > 0) {
          for (::std::size_t i = this->m_bits.size() - diff; i --> 0;) {
            this->m_bits[i] <<= pos % W;
            if (i > 0) {
              this->m_bits[i] |= this->m_bits[i - 1] >> (W - pos % W);
            }
          }
        }
        if (diff > 0) {
          for (::std::size_t i = this->m_bits.size() - diff; i --> 0;) {
            this->m_bits[i + diff] = this->m_bits[i];
          }
          ::std::fill(this->m_bits.begin(), ::std::next(this->m_bits.begin(), diff), 0);
        }
        if (this->m_size % W > 0) {
          this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
        }
      } else {
        ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      }
      return *this;
    }
    ::tools::dynamic_bitset& operator>>=(const ::std::size_t pos) {
      const ::std::size_t diff = pos / W;
      if (diff < this->m_bits.size()) {
        if (pos % W > 0) {
          for (::std::size_t i = diff; i < this->m_bits.size(); ++i) {
            this->m_bits[i] >>= pos % W;
            if (i + 1 < this->m_bits.size()) {
              this->m_bits[i] |= this->m_bits[i + 1] << (W - pos % W);
            }
          }
        }
        if (diff > 0) {
          for (::std::size_t i = diff; i < this->m_bits.size(); ++i) {
            this->m_bits[i - diff] = this->m_bits[i];
          }
          ::std::fill(::std::next(this->m_bits.begin(), this->m_bits.size() - diff), this->m_bits.end(), 0);
        }
      } else {
        ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      }
      return *this;
    }
    ::tools::dynamic_bitset& set() {
      ::std::fill(this->m_bits.begin(), this->m_bits.end(), ::std::numeric_limits<::std::uint64_t>::max());
      if (this->m_size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
      }
      return *this;
    }
    ::tools::dynamic_bitset& set(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] |= UINT64_C(1) << (pos % W);
      return *this;
    }
    ::tools::dynamic_bitset& set(const ::std::size_t pos, const bool val) {
      return val ? this->set(pos) : this->reset(pos);
    }
    ::tools::dynamic_bitset& reset() {
      ::std::fill(this->m_bits.begin(), this->m_bits.end(), 0);
      return *this;
    }
    ::tools::dynamic_bitset& reset(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] &= ~(UINT64_C(1) << (pos % W));
      return *this;
    }
    ::tools::dynamic_bitset operator~() const {
      return ::tools::dynamic_bitset(*this).flip();
    }
    ::tools::dynamic_bitset& flip() {
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        this->m_bits[i] = ~this->m_bits[i];
      }
      if (this->m_size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (this->m_size % W)) - 1;
      }
      return *this;
    }
    ::tools::dynamic_bitset& flip(const ::std::size_t pos) {
      assert(pos < this->m_size);
      this->m_bits[pos / W] ^= UINT64_C(1) << (pos % W);
      return *this;
    }
    reference operator[](const ::std::size_t pos) {
      return reference(this, pos);
    }
    bool operator[](const ::std::size_t pos) const {
      return this->test(pos);
    }
    ::std::size_t count() const {
      ::std::size_t result = 0;
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        result += ::std::popcount(this->m_bits[i]);
      }
      return result;
    }
    ::std::size_t size() const {
      return this->m_size;
    }
    bool test(const ::std::size_t pos) const {
      assert(pos < this->m_size);
      return (this->m_bits[pos / W] >> (pos % W)) & 1;
    }
    bool all() const {
      if (this->m_size % W > 0) {
        for (::std::size_t i = 0; i + 1 < this->m_bits.size(); ++i) {
          if (this->m_bits[i] != ::std::numeric_limits<::std::uint64_t>::max()) {
            return false;
          }
        }
        return this->m_bits.back() == (UINT64_C(1) << (this->m_size % W)) - 1;
      } else {
        for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
          if (this->m_bits[i] != ::std::numeric_limits<::std::uint64_t>::max()) {
            return false;
          }
        }
        return true;
      }
    }
    bool any() const {
      for (::std::size_t i = 0; i < this->m_bits.size(); ++i) {
        if (this->m_bits[i] != 0) {
          return true;
        }
      }
      return false;
    }
    bool none() const {
      return !this->any();
    }
    ::std::string to_string() const {
      ::std::ostringstream oss;
      oss << *this;
      return oss.str();
    }
    friend bool operator==(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return lhs.m_size == rhs.m_size && lhs.m_bits == rhs.m_bits;
    }
    friend bool operator!=(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return !(lhs == rhs);
    }
    ::tools::dynamic_bitset operator<<(const ::std::size_t pos) const {
      return ::tools::dynamic_bitset(*this) <<= pos;
    }
    ::tools::dynamic_bitset operator>>(const ::std::size_t pos) const {
      return ::tools::dynamic_bitset(*this) >>= pos;
    }
    friend ::tools::dynamic_bitset operator&(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) &= rhs;
    }
    friend ::tools::dynamic_bitset operator|(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) |= rhs;
    }
    friend ::tools::dynamic_bitset operator^(const ::tools::dynamic_bitset& lhs, const ::tools::dynamic_bitset& rhs) {
      return ::tools::dynamic_bitset(lhs) ^= rhs;
    }
    friend ::std::istream& operator>>(::std::istream& is, ::tools::dynamic_bitset& self) {
      ::std::string s;
      is >> s;
      self = ::tools::dynamic_bitset(s);
      return is;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::dynamic_bitset& self) {
      for (::std::size_t i = self.m_bits.size(); i --> 0;) {
        for (::std::size_t j = i + 1 < self.m_bits.size() ? W : (self.m_size - 1) % W + 1; j --> 0;) {
          os << ((self.m_bits[i] >> j) & 1);
        }
      }
      return os;
    }
    bool empty() const {
      return this->m_size == 0;
    }
    void resize(const ::std::size_t size) {
      this->m_size = size;
      this->m_bits.resize(::tools::ceil(size, W));
      if (size % W > 0) {
        this->m_bits.back() &= (UINT64_C(1) << (size % W)) - 1;
      }
    }
    void shrink_to_fit() {
      this->m_bits.shrink_to_fit();
    }
  private:
    ::std::size_t Find_first(const ::std::size_t offset) const {
      for (::std::size_t i = offset; i < this->m_bits.size(); ++i) {
        if (this->m_bits[i] > 0) {
          return i * W + ::std::countr_zero(this->m_bits[i]);
        }
      }
      return this->m_size;
    }
  public:
    ::std::size_t Find_first() const {
      return this->Find_first(0);
    }
    ::std::size_t Find_next(const ::std::size_t pos) const {
      assert(pos < this->m_size);

      if (pos % W == W - 1) return this->Find_first((pos + 1) / W);
      if (const auto x = this->m_bits[pos / W] >> (pos % W + 1); x > 0) return pos + ::std::countr_zero(x) + 1;
      return this->Find_first(pos / W + 1);
    }
  };
}


#line 7 "tests/scc_graph/edges_to_scc.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, M;
  std::cin >> N >> M;
  tools::scc_graph graph(N);
  for (ll i = 0; i < M; ++i) {
    ll A, B;
    std::cin >> A >> B;
    --A, --B;
    graph.add_edge(A, B);
  }

  graph.build();

  std::vector<tools::dynamic_bitset> dp(graph.sccs().size(), tools::dynamic_bitset(N));
  for (ll i = graph.sccs().size() - 1; i >= 0; --i) {
    for (const auto v : graph.sccs()[i]) {
      dp[i].set(v);
    }
    for (const auto& [j, unused] : graph.edges_to_scc(i)) {
      dp[j] |= dp[i];
    }
  }

  ll answer = 0;
  for (ll i = 0; i < N; ++i) {
    answer += dp[graph.scc_id(i)].count();
  }
  std::cout << answer << '\n';
  return 0;
}
Back to top page