辞書順最大/最小のトポロジカルソート
(src/graph/topological-ordering/lexical-order-topological-sort.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/graph/topological-ordering/lexical-order-topological-sort.hpp"

Appendix

テンプレートパラメータに渡すグラフ $G$ の仕様について

lexical_order_topological_sort

std::vector< usize >
lexical_order_topological_sort(
  const G &g
)

辞書順最大、または辞書順最小のトポロジカル順序を求める。

非連結な場合や DAG でない場合は空の std::vector が返る。

usage

辞書順最小を求める場合

lexical_order_topological_sort< G, std::greater< usize > >(g)

辞書順最大を求める場合

lexical_order_topological_sort< G, std::less< usize > >(g)

制約

• Compare には std::greater< usize > または std::less< usize > が渡されること。

計算量

• $O(|E| + |V| \log |V|)$

Depends on

• size alias (src/cpp-template/header/size-alias.hpp)

Verified with

• test/atcoder/abc291_e.test.cpp

Code

#include "src/cpp-template/header/size-alias.hpp"

#include <queue>
#include <vector>

namespace luz {

  template < class G, class Compare >
  std::vector< usize > lexical_order_topological_sort(const G &g) {
    usize n = g.size();

    std::vector< usize > indegrees(n);
    for (auto v: rep(0, n)) {
      for (auto &&e: g[v]) {
        indegrees[e.to]++;
      }
    }

    std::priority_queue< usize, std::vector< usize >, Compare > pq;
    for (usize v: rep(0, n)) {
      if (indegrees[v]) continue;
      pq.emplace(v);
    }

    std::vector< usize > result;
    result.reserve(n);
    while (not pq.empty()) {
      auto v = pq.top();
      pq.pop();

      result.emplace_back(v);
      for (auto &&e: g[v]) {
        if (--indegrees[e.to]) continue;
        pq.emplace(e.to);
      }
    }

    if (result.size() != n) {
      return {};
    }

    return result;
  }

} // namespace luz

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 2 "src/graph/topological-ordering/lexical-order-topological-sort.hpp"

#include <queue>
#include <vector>

namespace luz {

  template < class G, class Compare >
  std::vector< usize > lexical_order_topological_sort(const G &g) {
    usize n = g.size();

    std::vector< usize > indegrees(n);
    for (auto v: rep(0, n)) {
      for (auto &&e: g[v]) {
        indegrees[e.to]++;
      }
    }

    std::priority_queue< usize, std::vector< usize >, Compare > pq;
    for (usize v: rep(0, n)) {
      if (indegrees[v]) continue;
      pq.emplace(v);
    }

    std::vector< usize > result;
    result.reserve(n);
    while (not pq.empty()) {
      auto v = pq.top();
      pq.pop();

      result.emplace_back(v);
      for (auto &&e: g[v]) {
        if (--indegrees[e.to]) continue;
        pq.emplace(e.to);
      }
    }

    if (result.size() != n) {
      return {};
    }

    return result;
  }

} // namespace luz

Back to top page