Conexiones en un grafo P32618


Statement
 

pdf   zip

thehtml

Dado un grafo con n vértices, calculad cuántos subconjuntos de dos vértices x e y son tales que hay algún camino desde x hasta y, y también algún camino desde y hasta x.

Tened en cuenta que el grafo dado puede ser dirigido o no dirigido. En el primer caso una conexión directa entre x e y consiste en un arco dirigido desde x hasta y, mientras que en el segundo caso consiste en una arista bidireccional que conecta x e y en ambos sentidos.

Entrada

La entrada consiste en diversos casos, cada uno con un carácter ‘D’ o ‘N’ que indica si el grafo es dirigido o no, seguido de n, seguida del número de arcos o aristas m. Siguen m pares de vértices x y, con xy, indicando cada arco o arista. Suponed 1 ≤ n ≤ 3 · 104, 0 ≤ m ≤ 5n, que los vértices se numeran a partir de 0, y que no hay arcos o aristas repetidos.

Salida

Para cada caso, escribid el número de subconjuntos de dos vértices mutuamente accesibles entre sí.

Puntuación

  • Test-1:  ‍ Entradas donde n ≤ 10.  ‍10 Puntos ‍
  • Test-2:  ‍ Entradas donde n ≤ 50.  ‍20 Puntos ‍
  • Test-3:  ‍ Entradas sólo con grafos no dirigidos.  ‍20 Puntos ‍
  • Test-4:  ‍ Entradas de todo tipo.  ‍50 Puntos ‍
Public test cases
  • Input

    D 2 2
    0 1
    1 0
    
    N 6 4
    1 2
    0 5
    5 3
    3 0
    
    D 6 4
    1 2
    0 5
    5 3
    3 0
    

    Output

    1
    4
    3
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++