Màxima accessibilitat P70158


Statement
 

pdf   zip

thehtml

Donat un graf dirigit, definim l’accessibilitat de cada vèrtex v com el nombre de vèrtexs des dels quals es pot arribar fins a v fent tants passos com calgui. Podeu calcular la màxima de les accessibilitats de tots els vèrtexs d’un graf?

Entrada

L’entrada consisteix en diversos grafs, cadascun amb el nombre de vèrtexs n i el nombre d’arcs m, seguits d’m parells x y indicant un arc des d’x fins a y, amb xy. Suposeu 1 ≤ n ≤ 104, 0 ≤ m ≤ 10n, que no hi ha cap arc repetit, i que els vèrtexs es numeren entre 0 i n − 1.

Sortida

Per a cada graf, escriviu la màxima accessibilitat dels seus vèrtexs.

Observacions

  • Tots els grafs dels jocs de proves privats s’han generat a l’atzar.
  • Es poden obtenir 50 punts amb una solució no gaire eficient. Per obtenir els 100 punts cal tractar eficientment grafs amb n gran i amb nm ≤ 10n.
Public test cases
  • Input

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

    Output

    2
    4
    5
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++