tests/tsort/query.test.cpp

View this file on GitHub
Last update: 2025-05-10 18:18:44+09:00
Link: https://onlinejudge.u-aizu.ac.jp/problems/GRL_4_B

Depends on

Code

// competitive-verifier: STANDALONE
// oj-verify currently cannot handle https://onlinejudge.u-aizu.ac.jp/problems/GRL_4_B properly, so I implemented a special judge for the problem.

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

void verify(const tools::tsort& graph) {
  const tools::permutation<int> result(graph.query());
  assert_that(result.size() == graph.size());
  for (const auto& edge : graph.edges()) {
    assert_that(result.inv(edge.from) < result.inv(edge.to));
  }
}

void sample_00() {
  tools::tsort graph(6);
  graph.add_edge(0, 1);
  graph.add_edge(1, 2);
  graph.add_edge(3, 1);
  graph.add_edge(3, 4);
  graph.add_edge(4, 5);
  graph.add_edge(5, 2);
  verify(graph);
}

void small_00() {
  tools::tsort graph(5);
  graph.add_edge(0, 1);
  graph.add_edge(0, 2);
  graph.add_edge(2, 3);
  graph.add_edge(2, 4);
  graph.add_edge(3, 4);
  verify(graph);
}

void small_01() {
  tools::tsort graph(6);
  graph.add_edge(0, 1);
  graph.add_edge(0, 3);
  graph.add_edge(0, 2);
  graph.add_edge(2, 3);
  graph.add_edge(1, 4);
  graph.add_edge(3, 5);
  graph.add_edge(4, 5);
  verify(graph);
}

void small_02() {
  tools::tsort graph(8);
  graph.add_edge(0, 1);
  graph.add_edge(0, 2);
  graph.add_edge(2, 1);
  graph.add_edge(1, 3);
  graph.add_edge(2, 3);
  graph.add_edge(2, 4);
  graph.add_edge(3, 4);
  graph.add_edge(3, 5);
  graph.add_edge(4, 6);
  graph.add_edge(5, 7);
  graph.add_edge(6, 7);
  verify(graph);
}

void small_03() {
  tools::tsort graph(8);
  graph.add_edge(0, 1);
  graph.add_edge(0, 3);
  graph.add_edge(1, 2);
  graph.add_edge(4, 5);
  graph.add_edge(4, 7);
  graph.add_edge(5, 7);
  graph.add_edge(7, 6);
  verify(graph);
}

void small_04() {
  tools::tsort graph(8);
  graph.add_edge(0, 7);
  graph.add_edge(1, 7);
  graph.add_edge(2, 7);
  graph.add_edge(3, 7);
  graph.add_edge(4, 7);
  graph.add_edge(5, 7);
  graph.add_edge(6, 7);
  verify(graph);
}

void small_05() {
  tools::tsort graph(9);
  graph.add_edge(1, 2);
  graph.add_edge(3, 4);
  graph.add_edge(5, 6);
  graph.add_edge(7, 8);
  graph.add_edge(0, 2);
  graph.add_edge(0, 3);
  graph.add_edge(0, 6);
  graph.add_edge(0, 7);
  verify(graph);
}

void small_06() {
  tools::tsort graph(5);
  graph.add_edge(0, 1);
  graph.add_edge(0, 2);
  graph.add_edge(2, 3);
  graph.add_edge(2, 4);
  graph.add_edge(3, 4);
  verify(graph);
}

void corner_00() {
  tools::tsort graph(2);
  graph.add_edge(0, 1);
  verify(graph);
}

void corner_01() {
  tools::tsort graph(2);
  verify(graph);
}

void corner_02() {
  tools::tsort graph(4);
  graph.add_edge(0, 1);
  graph.add_edge(2, 3);
  verify(graph);
}

void corner_03() {
  tools::tsort graph(3);
  graph.add_edge(0, 2);
  graph.add_edge(1, 2);
  verify(graph);
}

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

  sample_00();
  small_00();
  small_01();
  small_02();
  small_03();
  small_04();
  small_05();
  small_06();
  corner_00();
  corner_01();
  corner_02();
  corner_03();

  return 0;
}

#line 1 "tests/tsort/query.test.cpp"
// competitive-verifier: STANDALONE
// oj-verify currently cannot handle https://onlinejudge.u-aizu.ac.jp/problems/GRL_4_B properly, so I implemented a special judge for the problem.

#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/permutation.hpp"



#include <algorithm>
#include <cassert>
#include <cstddef>
#line 8 "tools/permutation.hpp"
#include <iterator>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

namespace tools {
  template <typename T>
  class permutation {
    ::std::vector<int> m_perm;
    ::std::vector<int> m_inv;

    void verify_consistency() const {
#ifndef NDEBUG
      ::std::vector<bool> unique(this->size(), true);
      for (const auto x : this->m_perm) {
        assert(0 <= x && x < this->size());
        assert(unique[x]);
        unique[x] = false;
      }
#endif
    }

    void make_inv() {
      this->m_inv.resize(this->size());
      for (int i = 0; i < this->size(); ++i) {
        this->m_inv[this->m_perm[i]] = i;
      }
    }

  public:
    class iterator {
      ::std::vector<int>::const_iterator m_it;

    public:
      using reference = T;
      using value_type = T;
      using difference_type = ::std::ptrdiff_t;
      using pointer = const value_type*;
      using iterator_category = ::std::random_access_iterator_tag;

      iterator() = default;
      iterator(const ::std::vector<int>::const_iterator it) : m_it(it) {
      }

      reference operator*() const {
        return *this->m_it;
      }

      iterator& operator++() {
        ++this->m_it;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_it;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_it += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_it -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_it + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_it - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        return lhs.m_it - rhs.m_it;
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend bool operator==(const iterator lhs, const iterator rhs) {
        return lhs.m_it == rhs.m_it;
      }
      friend bool operator!=(const iterator lhs, const iterator rhs) {
        return lhs.m_it != rhs.m_it;
      }
      friend bool operator<(const iterator lhs, const iterator rhs) {
        return lhs.m_it < rhs.m_it;
      }
      friend bool operator<=(const iterator lhs, const iterator rhs) {
        return lhs.m_it <= rhs.m_it;
      }
      friend bool operator>(const iterator lhs, const iterator rhs) {
        return lhs.m_it > rhs.m_it;
      }
      friend bool operator>=(const iterator lhs, const iterator rhs) {
        return lhs.m_it >= rhs.m_it;
      }
    };

    permutation() = default;
    explicit permutation(const int n) : m_perm(n), m_inv(n) {
      ::std::iota(this->m_perm.begin(), this->m_perm.end(), 0);
      ::std::iota(this->m_inv.begin(), this->m_inv.end(), 0);
    }
    template <::std::ranges::range R>
    permutation(R&& r) : m_perm(::std::ranges::begin(r), ::std::ranges::end(r)) {
      this->verify_consistency();
      this->make_inv();
    }

    int size() const {
      return this->m_perm.size();
    }
    T operator[](const int i) const {
      assert(0 <= i && i < this->size());
      return this->m_perm[i];
    }
    iterator begin() const {
      return this->m_perm.begin();
    }
    iterator end() const {
      return this->m_perm.end();
    }

    ::tools::permutation<T>& swap_from_left(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      this->m_inv[this->m_perm[y]] = x;
      this->m_inv[this->m_perm[x]] = y;
      ::std::swap(this->m_perm[x], this->m_perm[y]);
      return *this;
    }
    ::tools::permutation<T>& swap_from_right(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      this->m_perm[this->m_inv[y]] = x;
      this->m_perm[this->m_inv[x]] = y;
      ::std::swap(this->m_inv[x], this->m_inv[y]);
      return *this;
    }

    long long id() const {
      if (this->size() == 0) return 0;

      ::std::vector<int> left(this->size());
      ::std::iota(left.begin(), left.end(), 0);

      ::std::vector<long long> fact(this->size());
      fact[0] = 1;
      for (int i = 1; i < this->size(); ++i) {
        fact[i] = fact[i - 1] * i;
      }

      long long id = 0;
      for (int i = 0; i < this->size(); ++i) {
        auto it = ::std::lower_bound(left.begin(), left.end(), this->m_perm[i]);
        id += ::std::distance(left.begin(), it) * fact[this->size() - 1 - i];
        left.erase(it);
      }

      return id;
    }

    static ::tools::permutation<T> from(const int n, long long id) {
      if (n == 0) return ::tools::permutation<T>(0);

      ::std::vector<int> left(n);
      ::std::iota(left.begin(), left.end(), 0);

      ::std::vector<long long> fact(n);
      fact[0] = 1;
      for (int i = 1; i < n; ++i) {
        fact[i] = fact[i - 1] * i;
      }

      ::std::vector<int> p;
      for (int i = 0; i < n; ++i) {
        const auto it = ::std::next(left.begin(), id / fact[n - i - 1]);
        p.push_back(*it);
        left.erase(it);
        id %= fact[n - i - 1];
      }

      return ::tools::permutation<T>(p);
    }

    ::tools::permutation<T> inv() const {
      return ::tools::permutation<T>(this->m_inv);
    }
    ::tools::permutation<T>& inv_inplace() {
      this->m_perm.swap(this->m_inv);
      return *this;
    }
    T inv(const int i) const {
      assert(0 <= i && i < this->size());
      return this->m_inv[i];
    }

    ::tools::permutation<T>& operator*=(const ::tools::permutation<T>& other) {
      assert(this->size() == other.size());
      for (int i = 0; i < this->size(); ++i) {
        this->m_inv[i] = other.m_perm[this->m_perm[i]];
      }
      this->m_perm.swap(this->m_inv);
      this->make_inv();
      return *this;
    }
    friend ::tools::permutation<T> operator*(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return ::tools::permutation<T>(lhs) *= rhs;
    }

    friend bool operator==(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return lhs.m_perm == rhs.m_perm;
    }
    friend bool operator!=(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return lhs.m_perm != rhs.m_perm;
    }

    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::permutation<T>& self) {
      os << '(';
      auto it = self.begin();
      const auto end = self.end();
      if (it != end) {
        os << *it;
        for (++it; it != end; ++it) {
          os << ", " << *it;
        }
      }
      return os << ')';
    }
    friend ::std::istream& operator>>(::std::istream& is, ::tools::permutation<T>& self) {
      for (auto& value : self.m_perm) {
        is >> value;
      }
      self.verify_consistency();
      self.make_inv();
      return is;
    }
  };
}


#line 1 "tools/tsort.hpp"



#line 5 "tools/tsort.hpp"
#include <cstdint>
#include <queue>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#line 6 "tools/pow2.hpp"

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 8 "tests/tsort/query.test.cpp"

void verify(const tools::tsort& graph) {
  const tools::permutation<int> result(graph.query());
  assert_that(result.size() == graph.size());
  for (const auto& edge : graph.edges()) {
    assert_that(result.inv(edge.from) < result.inv(edge.to));
  }
}

void sample_00() {
  tools::tsort graph(6);
  graph.add_edge(0, 1);
  graph.add_edge(1, 2);
  graph.add_edge(3, 1);
  graph.add_edge(3, 4);
  graph.add_edge(4, 5);
  graph.add_edge(5, 2);
  verify(graph);
}

void small_00() {
  tools::tsort graph(5);
  graph.add_edge(0, 1);
  graph.add_edge(0, 2);
  graph.add_edge(2, 3);
  graph.add_edge(2, 4);
  graph.add_edge(3, 4);
  verify(graph);
}

void small_01() {
  tools::tsort graph(6);
  graph.add_edge(0, 1);
  graph.add_edge(0, 3);
  graph.add_edge(0, 2);
  graph.add_edge(2, 3);
  graph.add_edge(1, 4);
  graph.add_edge(3, 5);
  graph.add_edge(4, 5);
  verify(graph);
}

void small_02() {
  tools::tsort graph(8);
  graph.add_edge(0, 1);
  graph.add_edge(0, 2);
  graph.add_edge(2, 1);
  graph.add_edge(1, 3);
  graph.add_edge(2, 3);
  graph.add_edge(2, 4);
  graph.add_edge(3, 4);
  graph.add_edge(3, 5);
  graph.add_edge(4, 6);
  graph.add_edge(5, 7);
  graph.add_edge(6, 7);
  verify(graph);
}

void small_03() {
  tools::tsort graph(8);
  graph.add_edge(0, 1);
  graph.add_edge(0, 3);
  graph.add_edge(1, 2);
  graph.add_edge(4, 5);
  graph.add_edge(4, 7);
  graph.add_edge(5, 7);
  graph.add_edge(7, 6);
  verify(graph);
}

void small_04() {
  tools::tsort graph(8);
  graph.add_edge(0, 7);
  graph.add_edge(1, 7);
  graph.add_edge(2, 7);
  graph.add_edge(3, 7);
  graph.add_edge(4, 7);
  graph.add_edge(5, 7);
  graph.add_edge(6, 7);
  verify(graph);
}

void small_05() {
  tools::tsort graph(9);
  graph.add_edge(1, 2);
  graph.add_edge(3, 4);
  graph.add_edge(5, 6);
  graph.add_edge(7, 8);
  graph.add_edge(0, 2);
  graph.add_edge(0, 3);
  graph.add_edge(0, 6);
  graph.add_edge(0, 7);
  verify(graph);
}

void small_06() {
  tools::tsort graph(5);
  graph.add_edge(0, 1);
  graph.add_edge(0, 2);
  graph.add_edge(2, 3);
  graph.add_edge(2, 4);
  graph.add_edge(3, 4);
  verify(graph);
}

void corner_00() {
  tools::tsort graph(2);
  graph.add_edge(0, 1);
  verify(graph);
}

void corner_01() {
  tools::tsort graph(2);
  verify(graph);
}

void corner_02() {
  tools::tsort graph(4);
  graph.add_edge(0, 1);
  graph.add_edge(2, 3);
  verify(graph);
}

void corner_03() {
  tools::tsort graph(3);
  graph.add_edge(0, 2);
  graph.add_edge(1, 2);
  verify(graph);
}

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

  sample_00();
  small_00();
  small_01();
  small_02();
  small_03();
  small_04();
  small_05();
  small_06();
  corner_00();
  corner_01();
  corner_02();
  corner_03();

  return 0;
}