Topological sorting (tools/tsort.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-10 18:18:44+09:00
• Include: #include "tools/tsort.hpp"

It is a class about topological sorting.

License

• CC0

Author

• anqooqie

Constructor

tsort graph(int n);

It creates a directed graph with $n$ vertices and $0$ edges.

Constraints

• $n \geq 0$

Time Complexity

• $O(n)$

size

int graph.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

add_edge

int graph.add_edge(int u, int v);

It adds a directed edge oriented from $u$ to $v$. It returns an integer $k$ such that this is the $k$-th edge that is added.

Constraints

• $0 \leq u < n$
• $0 \leq v < n$

Time Complexity

• $O(1)$ amortized

get_edge

struct edge {
  int from;
  int to;
};
edge graph.get_edge(int k);

It returns the $k$-th edge.

Constraints

• $0 \leq k < |E|$ where $|E|$ is the number of edges

Time Complexity

• $O(1)$

edges

std::vector<edge> graph.edges();

It returns all the edges in the graph. The edges are ordered in the same order as added by add_edge.

Constraints

• None

Time Complexity

• $O(1)$

query

std::vector<int> graph.query();

Topological sorting is a linear ordering of vertices such that for every directed edge from $u$ to $v$, vertex $u$ comes before $v$ in the ordering. It returns one of the topological sortings for the graph.

Constraints

• The graph is a DAG.

Time Complexity

• $O(n)$

count

template <typename R = long long>
R graph.count();

It returns the number of the topological sortings for the graph.

Constraints

• $n < 32$

Time Complexity

• $O(2^n n)$

Depends on

• $2^x$ (tools/pow2.hpp)

Verified with

• tests/tsort/count.test.cpp
• tests/tsort/query.test.cpp

Code

#ifndef TOOLS_TSORT_HPP
#define TOOLS_TSORT_HPP

#include <cassert>
#include <cstdint>
#include <queue>
#include <utility>
#include <vector>
#include "tools/pow2.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];
    }
  };
}

#endif

#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];
    }
  };
}

Back to top page