Camí màxim P50411


Statement
 

pdf   zip

html

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 x ≠ y. 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++