Clausura transitiva P19374

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 x ≠ y. 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 = Θ(n²).