This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://atcoder.jp/contests/abc291/tasks/abc291_e #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/vector-ios.hpp" #include "src/graph/class/edge/edge.hpp" #include "src/graph/class/static-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 = StaticGraph< edge >; usize n, m; std::cin >> n >> m; graph g(n); for ([[maybe_unused]] usize _: rep(0, m)) { usize t, f; std::cin >> t >> f; g.add_directed_edge(t - 1, f - 1); } g.initialize(); 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: rep(0, n)) { ans[ord[i]] = i + 1; } std::cout << ans << std::endl; } 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/rep.hpp" #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 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 2 "src/cpp-template/header/vector-ios.hpp" #line 4 "src/cpp-template/header/vector-ios.hpp" #include <iostream> #include <vector> namespace luz { template < typename T > std::ostream &operator<<(std::ostream &os, const std::vector< T > vs) { for (usize i: rep(0, vs.size())) { os << vs[i] << (i + 1 != vs.size() ? " " : ""); } return os; } template < typename T > std::istream &operator>>(std::istream &is, std::vector< T > &vs) { for (T &v: vs) { is >> v; } return is; } } // namespace luz #line 2 "src/graph/class/edge/edge.hpp" #line 4 "src/graph/class/edge/edge.hpp" #line 6 "src/graph/class/edge/edge.hpp" namespace luz { template < typename T > class Edge { public: using cost_type = T; usize from, to; T cost; usize id; Edge() = default; Edge(usize from_, usize to_, T cost_, usize id_) : from(from_), to(to_), cost(cost_), id(id_) {} }; template < typename T > using Edges = std::vector< Edge< T > >; } // namespace luz #line 2 "src/graph/class/static-graph.hpp" #line 5 "src/graph/class/static-graph.hpp" #line 7 "src/graph/class/static-graph.hpp" #include <cassert> #line 9 "src/graph/class/static-graph.hpp" namespace luz::internal { template < typename Iterator > class OutgoingEdges { Iterator f, l; public: OutgoingEdges(Iterator f, Iterator l): f(f), l(l) {} Iterator begin() const { return f; } Iterator end() const { return l; } usize size() const { return l - f; } auto &operator[](usize k) { assert(k < size()); return begin()[k]; } const auto &operator[](usize k) const { assert(k < size()); return begin()[k]; } }; } // namespace luz::internal namespace luz { template < typename Edge > class StaticGraph { using Edges = std::vector< Edge >; using iterator = typename Edges::iterator; using const_iterator = typename Edges::const_iterator; template < typename Iterator > using Es = internal::OutgoingEdges< Iterator >; protected: bool initialized; usize vertex_count; usize edge_count; Edges edges; std::vector< usize > outdegrees; public: using cost_type = typename Edge::cost_type; StaticGraph() = default; explicit StaticGraph(usize n) : initialized(false), vertex_count(n), edge_count(0), outdegrees(vertex_count) {} usize size() const { return vertex_count; } void initialize() { assert(not initialized); outdegrees.emplace_back(0); for (usize i: rrep(0, size())) { outdegrees[i] += outdegrees[i + 1]; } std::sort(edges.begin(), edges.end(), [](const Edge &e1, const Edge &e2) { return e1.from != e2.from ? e1.from > e2.from : e1.to < e2.to; }); initialized = true; } void add_directed_edge(usize from, usize to, cost_type cost = 1) { assert(not initialized); assert(from < size()); assert(to < size()); edges.emplace_back(from, to, cost, edge_count++); outdegrees[from]++; } void add_undirected_edge(usize u, usize v, cost_type cost = 1) { assert(not initialized); assert(u < size()); assert(v < size()); assert(u != v); edges.emplace_back(u, v, cost, edge_count); outdegrees[u]++; edges.emplace_back(v, u, cost, edge_count++); outdegrees[v]++; } Es< iterator > operator[](const usize &v) { assert(initialized); return Es< iterator >(edges.begin() + outdegrees[v + 1], edges.begin() + outdegrees[v]); } const Es< const_iterator > operator[](const usize &v) const { assert(initialized); return Es< const_iterator >(edges.cbegin() + outdegrees[v + 1], edges.cbegin() + outdegrees[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" 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 8 "test/atcoder/abc291_e.test.cpp" #include <functional> #line 11 "test/atcoder/abc291_e.test.cpp" namespace luz { void main_() { using edge = Edge< usize >; using graph = StaticGraph< edge >; usize n, m; std::cin >> n >> m; graph g(n); for ([[maybe_unused]] usize _: rep(0, m)) { usize t, f; std::cin >> t >> f; g.add_directed_edge(t - 1, f - 1); } g.initialize(); 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: rep(0, n)) { ans[ord[i]] = i + 1; } std::cout << ans << std::endl; } else { std::cout << "No" << std::endl; } } } // namespace luz int main() { luz::main_(); }