Camí més llarg P26922


Statement
 

pdf   zip

thehtml

Donat un graf dirigit sense cicles, calculeu-ne la longitud del camí més llarg.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n i el nombre d’arcs m, seguits de m parells diferents x y, amb xy, indicant un arc de x a y. Suposeu 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, que el graf no té cicles, i que els vèrtexs es numeren a partir de 0.

Sortida

Per a cada graf, escriviu la màxima longitud, calculada en nombre d’arcs, del camí més llarg.

Pista

La solució esperada és una programació 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
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++