tests/tsort/count.test.cpp

View this file on GitHub
Last update: 2025-05-10 18:18:44+09:00
Link: https://atcoder.jp/contests/abc041/tasks/abc041_d

Depends on

Code

// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc041/tasks/abc041_d

#include <iostream>
#include "tools/assert_that.hpp"
#include "tools/tsort.hpp"

void sample_01() {
  tools::tsort graph(3);
  graph.add_edge(1, 0);
  graph.add_edge(1, 2);
  assert_that(graph.count() == 2);
}

void sample_02() {
  tools::tsort graph(5);
  graph.add_edge(0, 1);
  graph.add_edge(1, 2);
  graph.add_edge(2, 4);
  graph.add_edge(0, 3);
  graph.add_edge(3, 4);
  assert_that(graph.count() == 3);
}

void sample_03() {
  tools::tsort graph(16);
  graph.add_edge(0, 1);
  assert_that(graph.count() == 10461394944000);
}

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

  sample_01();
  sample_02();
  sample_03();

  return 0;
}

#line 1 "tests/tsort/count.test.cpp"
// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc041/tasks/abc041_d

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



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/tsort.hpp"



#include <cassert>
#include <cstdint>
#include <queue>
#include <utility>
#include <vector>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#include <cstddef>

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 10 "tools/tsort.hpp"

namespace tools {
  class tsort {
  public:
    struct edge {
      int from;
      int to;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<int>> m_graph;

  public:
    tsort() = default;
    explicit tsort(const int n) : m_graph(n) {
    }

    int size() const {
      return this->m_graph.size();
    }

    int add_edge(const int u, const int v) {
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      this->m_edges.push_back({u, v});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const int k) const & {
      assert(0 <= k && k < this->m_edges.size());
      return this->m_edges[k];
    }
    edge get_edge(const int k) && {
      assert(0 <= k && k < this->m_edges.size());
      return ::std::move(this->m_edges[k]);
    }

    const ::std::vector<edge>& edges() const & {
      return this->m_edges;
    }
    ::std::vector<edge> edges() && {
      return ::std::move(this->m_edges);
    }

    ::std::vector<int> query() const {
      ::std::vector<int> indegs(this->size(), 0);
      for (int u = 0; u < this->size(); ++u) {
        for (const auto e : this->m_graph[u]) {
          ++indegs[this->m_edges[e].to];
        }
      }

      ::std::queue<int> queue;
      for (int v = 0; v < this->size(); ++v) {
        if (indegs[v] == 0) {
          queue.push(v);
        }
      }

      ::std::vector<int> result;
      result.reserve(this->size());
      while (!queue.empty()) {
        const auto u = queue.front();
        queue.pop();
        result.push_back(u);
        for (const auto e : this->m_graph[u]) {
          const auto v = this->m_edges[e].to;
          --indegs[v];
          if (indegs[v] == 0) {
            queue.push(v);
          }
        }
      }

      return result;
    }

    template <typename R = long long>
    R count() const {
      using u32 = ::std::uint_fast32_t;

      assert(this->size() < 32);

      ::std::vector<u32> graph(this->size());
      for (const auto& edge : this->m_edges) {
        graph[edge.from] |= u32(1) << edge.to;
      }

      ::std::vector<R> dp(::tools::pow2(this->size()));
      dp[0] = R(1);
      for (u32 state = 1; state < ::tools::pow2(this->size()); ++state) {
        dp[state] = R(0);
        for (int v = 0; v < this->size(); ++v) {
          if (const auto prev_state = state & ~(u32(1) << v); ((state >> v) & 1) && !(graph[v] & prev_state)) {
            dp[state] += dp[prev_state];
          }
        }
      }

      return dp[::tools::pow2(this->size()) - 1];
    }
  };
}


#line 7 "tests/tsort/count.test.cpp"

void sample_01() {
  tools::tsort graph(3);
  graph.add_edge(1, 0);
  graph.add_edge(1, 2);
  assert_that(graph.count() == 2);
}

void sample_02() {
  tools::tsort graph(5);
  graph.add_edge(0, 1);
  graph.add_edge(1, 2);
  graph.add_edge(2, 4);
  graph.add_edge(0, 3);
  graph.add_edge(3, 4);
  assert_that(graph.count() == 3);
}

void sample_03() {
  tools::tsort graph(16);
  graph.add_edge(0, 1);
  assert_that(graph.count() == 10461394944000);
}

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

  sample_01();
  sample_02();
  sample_03();

  return 0;
}