Puentes P37339


Statement
 

pdf   zip

thehtml

Un puente de un grafo no dirigido se define como cualquier arista cuyo borrado incrementa el número de componentes conexas del grafo. Vuestra tarea es calcular todos los puentes de un grafo dado.

Entrada

La entrada consiste en diversos casos, cada uno con el número de vértices n, seguido del número de aristas m, seguido de m pares x y indicando una arista entre x e y, con xy. Asumid 2 ≤ n ≤ 104, 1 ≤ m ≤ 5n, que los vértices se numeran a partir de cero, y que hay como mucho una arista conectando cualquier par de vértices.

Salida

Para cada grafo, escribid el número de puentes, seguido por una linea con todos los puentes. Los dos vértices de cada puente deben estar ordenados crecientemente, y los puentes entre sí también deben estar ordenados crecientemente. Escribid una linea con 10 guiones al final de cada caso.

Public test cases
  • Input

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

    Output

    1
    0 1
    ----------
    0
    
    ----------
    3
    0 1  0 3  1 2
    ----------
    2
    0 6  3 4
    ----------
    3
    0 4  1 5  3 4
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++