Транзитивное замыкание

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в $i$-й строке и $j$-м столбце находится 1, если от вершины $i$ можно добраться до вершины $j$, и 0 - иначе.

Входные данные

В первой строке дано число $N$ ($1 \le N \le 100$) - число вершин в графе. Далее задана матрица смежности графа: в $N$ строках даны по $N$ чисел 0 или 1 в каждой. $i$-е число в $i$-й строке всегда равно 1.

Выходные данные

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Примеры
Входные данные
4
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1
Выходные данные
1 1 1 0 
1 1 1 0 
1 1 1 0 
1 1 1 1

Задача на informatics

algoprog.ru © Петр Калинин, GNU AGPL, github.com/petr-kalinin/algoprog | О лицензии на материалы сайта | Блог