Language: C++

// #include "longest_path.h"
#include <algorithm>
#include <queue>
#include <stdexcept>

namespace {

Graph reverse(const Graph& graph);

std::vector<size_t> compute_in_degree(const Graph& graph);

std::queue<size_t>
all_nodes_with_zero_in_degree(const std::vector<size_t>& in_degree);

std::vector<size_t> topological_sort(const Graph& graph);

} // namespace

class Graph {
public:
    Graph(size_t n);

    void add_edge(size_t from, size_t to);

    size_t num_nodes() const;

    const std::vector<size_t>& neighbors(size_t n) const;

private:
    size_t n;
    std::vector<std::vector<size_t>> data =
        std::vector<std::vector<size_t>>(n + 1, std::vector<size_t>{});
};

Graph::Graph(size_t n)
    : n{n}
{
}

void Graph::add_edge(size_t from, size_t to) { data[from].push_back(to); }

size_t Graph::num_nodes() const { return n; }

const std::vector<size_t>& Graph::neighbors(size_t node) const
{
    return data[node];
}

size_t length_of_longest_path(const Graph& graph)
{
    std::vector<size_t> path_lengths(graph.num_nodes() + 1);
    const auto topological_order = topological_sort(graph);
    Graph reversed_graph = reverse(graph);

    for (auto node : topological_order) {
        size_t max{0};
        for (size_t neighbor : reversed_graph.neighbors(node)) {
            max = std::max(max, path_lengths[neighbor] + 1);
        }
        path_lengths[node] = max;
    }

    return *std::max_element(path_lengths.cbegin(), path_lengths.cend());
}

namespace {

// Implements Kahn's algorithm
std::vector<size_t> topological_sort(const Graph& graph)
{
    std::vector<size_t> order;
    order.reserve(graph.num_nodes());

    auto in_degree = compute_in_degree(graph);

    auto zero_in_degree_nodes = all_nodes_with_zero_in_degree(in_degree);

    while (!zero_in_degree_nodes.empty()) {
        const size_t current = zero_in_degree_nodes.front();
        order.push_back(current);
        zero_in_degree_nodes.pop();
        for (auto neighbor : graph.neighbors(current)) {
            --in_degree[neighbor];
            if (in_degree[neighbor] == 0)
                zero_in_degree_nodes.push(neighbor);
        }
    }

    // check if in_degree doesn't have all zeroes than graph is not DAG
    if (std::any_of(in_degree.cbegin(), in_degree.cend(), [](size_t incoming) {
            return incoming > 0;
        }))
        throw std::runtime_error{"Graph is not a DAG!"};

    return order;
}

std::vector<size_t> compute_in_degree(const Graph& graph)
{
    std::vector<size_t> in_degree(graph.num_nodes() + 1);
    for (size_t i = 1; i <= graph.num_nodes(); ++i)
        for (auto neighbor : graph.neighbors(i))
            ++in_degree[neighbor];
    return in_degree;
}

std::queue<size_t>
all_nodes_with_zero_in_degree(const std::vector<size_t>& in_degree)
{
    std::queue<size_t> zero_in_degree_nodes;
    for (int i = 1; i < in_degree.size(); ++i)
        if (in_degree[i] == 0)
            zero_in_degree_nodes.push(i);
    return zero_in_degree_nodes;
}

Graph reverse(const Graph& graph)
{
    Graph reversed_graph(graph.num_nodes());
    for (size_t i = 1; i <= graph.num_nodes(); ++i) {
        for (size_t neighbor : graph.neighbors(i)) {
            reversed_graph.add_edge(neighbor, i);
        }
    }
    return reversed_graph;
}

} // namespace

int main(int argc, char* argv[])
{
    size_t num_nodes, num_edges;
    std::cin >> num_nodes >> num_edges;
    Graph graph{num_nodes};
    for (size_t i = 0; i < num_edges; ++i) {
        size_t from, to;
        std::cin >> from >> to;
        graph.add_edge(from, to);
    }
    std::cout << length_of_longest_path(graph) << std::endl;
    return 0;
}


Compiler output:
a.cc:8:1: error: 'Graph' does not name a type
    8 | Graph reverse(const Graph& graph);
      | ^~~~~
a.cc:10:45: error: 'Graph' does not name a type
   10 | std::vector<size_t> compute_in_degree(const Graph& graph);
      |                                             ^~~~~
a.cc:15:44: error: 'Graph' does not name a type
   15 | std::vector<size_t> topological_sort(const Graph& graph);
      |                                            ^~~~~
a.cc: In function 'size_t length_of_longest_path(const Graph&)':
a.cc:52:53: error: invalid initialization of reference of type 'const int&' from expression of type 'const Graph'
   52 |     const auto topological_order = topological_sort(graph);
      |                                                     ^~~~~
a.cc:15:51: note: in passing argument 1 of 'std::vector<long unsigned int> {anonymous}::topological_sort(const int&)'
   15 | std::vector<size_t> topological_sort(const Graph& graph);
      |                                      ~~~~~~~~~~~~~^~~~~
a.cc:53:28: error: 'reverse' was not declared in this scope; did you mean 'std::reverse'?
   53 |     Graph reversed_graph = reverse(graph);
      |                            ^~~~~~~
      |                            std::reverse
In file included from /usr/include/c++/14/algorithm:86,
                 from a.cc:2:
/usr/include/c++/14/pstl/glue_algorithm_defs.h:249:1: note: 'std::reverse' declared here
  249 | reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last);
      | ^~~~~~~
a.cc: In function 'std::vector<long unsigned int> {anonymous}::topological_sort(const Graph&)':
a.cc:74:40: error: invalid initialization of reference of type 'const int&' from expression of type 'const Graph'
   74 |     auto in_degree = compute_in_degree(graph);
      |                                        ^~~~~
a.cc:10:52: note: in passing argument 1 of 'std::vector<long unsigned int> {anonymous}::compute_in_degree(const int&)'
   10 | std::vector<size_t> compute_in_degree(const Graph& graph);
      |                                       ~~~~~~~~~~~~~^~~~~
a.cc: In function 'int main(int, char**)':
a.cc:133:10: error: 'cin' is not a member of 'std'
  133 |     std::cin >> num_nodes >> num_edges;
      |          ^~~
a.cc:5:1: note: 'std::cin' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
    4 | #include <stdexcept>
  +++ |+#include <iostream>
    5 | 
a.cc:137:14: error: 'cin' is not a member of 'std'
  137 |         std::cin >> from >> to;
      |              ^~~
a.cc:137:14: note: 'std::cin' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
a.cc:140:10: error: 'cout' is not a member of 'std'
  140 |     std::cout << length_of_longest_path(graph) << std::endl;
      |          ^~~~
a.cc:140:10: note: 'std::cout' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
a.cc:140:56: error: 'endl' is not a member of 'std'
  140 |     std::cout << length_of_longest_path(graph) << std::endl;
      |                                                        ^~~~
a.cc:5:1: note: 'std::endl' is defined in header '<ostream>'; this is probably fixable by adding '#include <ostream>'
    4 | #include <stdexcept>
  +++ |+#include <ostream>
    5 |