Camí màxim P50411


Statement
 

pdf   zip

thehtml

Considereu un graf dirigit sense cicles amb n vèrtexs i m arcs. Els vèrtexs estan numerats entre 1 i n. Sigui ℓ la longitud del camí més llarg que acaba en el vèrtex n. Des de quants vèrtexs surt un camí de mida ℓ que acabi en el vèrtex n?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguit d’m parells x y indicant un arc d’x a y, amb xy. Suposeu 2 ≤ n ≤ 105, 0 ≤ m ≤ 5n, i que no hi ha arcs repetits.

Sortida

Per a cada cas, escriviu el nombre de vèrtexs des dels quals surt un camí de mida ℓ que arriba al vèrtex n.

Observació

Recomanem resoldre aquest problema en C++.

Public test cases
  • Input

    3 3
    1 2  2 3  1 3
    2 0
    
    7 8
    5 7  6 2  1 4  3 2  3 5  7 1  2 7  3 7
    

    Output

    1
    1
    2
    
  • Information
    Author
    Óscar Garries
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++