Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.
Camino más largo P26922
Dado un grafo dirigido sin ciclos, calculad la longitud de su camino más largo.
Entrada
La entrada consiste en diversos casos, cada uno con el número de vértices n y el número de arcos m, seguidos de m pares diferentes x y, con x ≠ y, indicando un arco de x a y. Suponed 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, que el grafo no tiene ciclos, y que los vértices se numeran a partir de 0.
Salida
Para cada grafo, escribid la máxima longitud, calculada en número de arcos, de su camino más largo.
Pista
La solución esperada es una programación dinámica recursiva.
Public test cases
Input
2 1 1 0 3 0 6 6 3 0 1 4 2 3 2 5 3 1 5 1
Output
1 0 3
Information
- Author
- Salvador Roura
- Language
- Spanish
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++