Camino más largo P26922


Statement
 

pdf   zip

thehtml

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 xy, 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++