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 \times 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 \ne y$. Suposeu $1 \le n \le 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 = \Theta(n^2)$.