Clausura transitiva P19374


Statement
 

pdf   zip

thehtml

Feu un programa que calculi la clausura (reflexivo) transitiva d’un graf dirigit amb n vèrtexs. És a dir, cal calcular una matriu n × n on a la columna j de la fila i hi hagi un 1 si es pot anar des de i fins a j, i hi hagi un 0 altrament.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n seguit del nombre d’arcs m. Segueixen m parells x y indicant un arc des de x fins a y, amb xy. Suposeu 1 ≤ n ≤ 200, que els vèrtexs es numeren entre 0 i n − 1, i que no hi ha arcs repetits.

Sortida

Per a cada graf, escriviu-ne la clausura transitiva, seguida d’una línia amb 20 guions.

Observació

En els jocs de proves privats “grossos”, es té m = Θ(n2).

Public test cases
  • Input

    2 1
    0 1
    
    1 0
    
    4 5
    1 0  2 3  3 1  2 1  3 0
    

    Output

    1 1
    0 1
    --------------------
    1
    --------------------
    1 0 0 0
    1 1 0 0
    1 1 1 1
    1 1 0 1
    --------------------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++