【模板】传递闭包(Transitive Closure)

题目描述

给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。

一张图的邻接矩阵定义为一个 $n\times n$ 的矩阵 $A=(a_{ij})_{n\times n}$，其中

$a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right.$

一张图的传递闭包定义为一个 $n\times n$ 的矩阵 $B=(b_{ij})_{n\times n}$，其中

$b_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right.$

输入格式

输入数据共 $n+1$ 行。

第一行一个正整数 $n$。

第 $2$ 到 $n+1$ 行每行 $n$ 个整数，第 $i+1$ 行第 $j$ 列的整数为 $a_{ij}$。

输出格式

输出数据共 $n$ 行。

第 $1$ 到 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数为 $b_{ij}$。

样例输入 #1

4
0 0 0 1
1 0 0 0
0 0 0 1
0 1 0 0

样例输出 #1

1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

数据范围

对于 $100\%$ 的数据，$1\le n\le 100$，保证 $a_{ij}\in\{0,1\}$ 且 $a_{ii}=0$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1200。

测试点分布

出处：原题链接