Avaries P67717


Statement
 

pdf   zip

html

La xarxa de trens d’un país molt petit està formada per n estacions, unides entre sí per m vies bidireccionals. La xarxa és connexa. Com que es volen acollir els propers Jocs Olímpics d’Hivern, el govern del país ha decidit fer un estudi de la robustesa de la xarxa de transport. En particular, es vol saber, per a cada estació x, en quants components connexos quedaria separada la xarxa si hi hagués una avaria. Podeu calcular-ho eficientment?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguits d’m parells x y, indicant una via entre x i y, amb x ≠ y. Les estacions es numeren entre 0 i n−1. No hi ha vies repetides. Podeu suposar 2 ≤ n ≤ 105 i 1 ≤ m ≤ 3 · 105.

Sortida

Per cada cas, i per a cada estació, indiqueu el nombre de components connexos en què quedaria dividida la xarxa si hi hagués una avaria en aquella estació. Escriviu una línia amb 10 guions al final de cada cas.

Puntuació

  • Cas A:   Casos on la xarxa té, com a molt, un cicle.  45% Punts 
  • Cas B:   Resta de casos.  55% Punts 

Observació

Us recomanem resoldre aquest problema en C++.

Public test cases

  • Input

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

4 4
0 1
1 2
2 3
3 1

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

    Output

    0: 1
1: 3
2: 1
3: 2
4: 1
5: 1
6: 1
----------
0: 1
1: 2
2: 1
3: 1
----------
0: 1
1: 1
2: 1
3: 1
4: 4
5: 1
6: 1
----------
    • Information
    Author
    Xavier Povill
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++