test/atcoder/abc291_e.test.cpp

• View this file on GitHub
• Last update: 2023-06-20 08:43:53+09:00
• Problem: https://atcoder.jp/contests/abc291/tasks/abc291_e

Depends on

• src/cpp-template/header/size-alias.hpp
• src/graph/class/dynamic-graph.hpp
• src/graph/class/edge/edge.hpp
• src/graph/topological-ordering/lexical-order-topological-sort.hpp

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/abc291/tasks/abc291_e

#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/class/edge/edge.hpp"
#include "src/graph/class/dynamic-graph.hpp"
#include "src/graph/topological-ordering/lexical-order-topological-sort.hpp"

#include <functional>
#include <iostream>

namespace luz {

  void main_() {
    using edge  = Edge< usize >;
    using graph = DynamicGraph< edge >;

    usize n, m;
    std::cin >> n >> m;

    graph g(n);
    while (m--) {
      usize t, f;
      std::cin >> t >> f;
      g.add_directed_edge(t - 1, f - 1);
    }

    auto ord =
        lexical_order_topological_sort< graph,
                                        std::greater< usize > >(g);
    auto rev =
        lexical_order_topological_sort< graph, std::less< usize > >(
            g);

    if (ord == rev) {
      std::cout << "Yes" << std::endl;

      std::vector< usize > ans(n);
      for (usize i = 0; i < n; i++) {
        ans[ord[i]] = i + 1;
      }

      for (usize i = 0; i < n; i++) {
        std::cout << ans[i] << (i + 1 == n ? '\n' : ' ');
      }
    } else {
      std::cout << "No" << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/atcoder/abc291_e.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc291/tasks/abc291_e

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

#include <cstddef>

namespace luz {

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

}
#line 2 "src/graph/class/edge/edge.hpp"

#line 4 "src/graph/class/edge/edge.hpp"

namespace luz {

  template < typename T >
  struct Edge {
    using cost_type = T;

    usize from, to;
    T cost;
    usize id;

    Edge() = default;
    
    Edge(usize f, usize t, T c, usize i) : from(f), to(t), cost(c), id(i) {}
  };

} // namespace luz
#line 2 "src/graph/class/dynamic-graph.hpp"

#line 4 "src/graph/class/dynamic-graph.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename Edge >
  class DynamicGraph {

    using Edges = std::vector< Edge >;

   protected:
    std::vector< Edges > g;
    usize edge_count;

   public:
    using cost_type = typename Edge::cost_type;

    DynamicGraph() = default;
    explicit DynamicGraph(usize n): g(n), edge_count(0) {}

    usize size() const {
      return g.size();
    }

    void add_directed_edge(usize from, usize to, cost_type cost = 1) {
      g[from].emplace_back(from, to, cost, edge_count++);
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(u != v);
      g[u].emplace_back(u, v, cost, edge_count);
      g[v].emplace_back(v, u, cost, edge_count++);
    }

    Edges operator[](const usize &v) {
      return g[v];
    }

    const Edges operator[](const usize &v) const {
      return g[v];
    }

  };

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

#include <queue>
#line 5 "src/graph/topological-ordering/lexical-order-topological-sort.hpp"

// usage
// - min: lexical_order_topological_sort< G, std::greater< usize > >(g);
// - max: lexical_order_topological_sort< G, std::less< usize > >(g);
// !!! it returns {} if G is disconnected or not DAG.
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 (usize v = 0; v < n; v++) {
      for (auto &&e: g[v]) {
        indegrees[e.to]++;
      }
    }

    std::priority_queue< usize, std::vector< usize >, Compare > pq;
    for (usize v = 0; v < n; v++) {
      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 7 "test/atcoder/abc291_e.test.cpp"

#include <functional>
#include <iostream>

namespace luz {

  void main_() {
    using edge  = Edge< usize >;
    using graph = DynamicGraph< edge >;

    usize n, m;
    std::cin >> n >> m;

    graph g(n);
    while (m--) {
      usize t, f;
      std::cin >> t >> f;
      g.add_directed_edge(t - 1, f - 1);
    }

    auto ord =
        lexical_order_topological_sort< graph,
                                        std::greater< usize > >(g);
    auto rev =
        lexical_order_topological_sort< graph, std::less< usize > >(
            g);

    if (ord == rev) {
      std::cout << "Yes" << std::endl;

      std::vector< usize > ans(n);
      for (usize i = 0; i < n; i++) {
        ans[ord[i]] = i + 1;
      }

      for (usize i = 0; i < n; i++) {
        std::cout << ans[i] << (i + 1 == n ? '\n' : ' ');
      }
    } else {
      std::cout << "No" << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}

Back to top page