Transitive closure P19374


Statement
 

pdf   zip

thehtml

Write a program to compute the transitive closure of a directed graph with n vertices. That is, you must compute an n × n matrix where at the j-th column of the i-th row there is a 1 if it is possible to go from i to j, and there is a 0 otherwise.

Input

Input consists of several cases. Every case begins with n followed by the number of arcs m. Follow m pairs x y to indicate an arc from x to y, with xy. Assume 1 ≤ n ≤ 200, that the vertices are numbered between 0 and n − 1, and that there are no repeated arcs.

Output

For every graph, print its transitive closure, followed by a line with 20 dashes.

Observation

In the “large” private test cases, we have 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
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++