Camins més llargs P54384


Statement
 

pdf   zip

thehtml

Feu un programa que, donat un graf dirigit sense cicles, calculi el nombre de vèrtexs del camí més llarg del graf. A més, cal calcular quants camins tenen aquesta longitud.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arestes m. Segueixen m parells x ⁠ ⁠ y indicant que hi ha un arc de x a y. No hi ha arcs repetits. Els vèrtexs es numeren començant en 0. Suposeu 1 ≤ n ≤ 104 i 0 ≤ m ≤ 5n.

Sortida

Per a cada cas, escriviu dos nombres: la longitud del camí més llarg, i quants camins tenen aquesta longitud. Els jocs de proves són tals que els dos nombres caben en un enter.

Public test cases

  • Input

    3 3
0 1  1 2  0 2

5 0

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

    Output

    3 1
1 5
4 4
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++