/ AKIOI OJ / 题库 /

【模板】传递闭包

【模板】传递闭包

出题人太菜，暂无测试数据。

题目描述

给定一张点数为nn的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。
一张图的邻接矩阵定义为一个n×nn \times n的矩阵 A=(ai,j)n×nA = (a_{i,j})_{n \times n}，其中ai,j=1a_{i, j} = 1表示ii到jj存在直接连边，ai,j=0a_{i, j} = 0表示ii到jj没有直接连边。
一张图的传递闭包定义为一个n×nn \times n的矩阵 B=(bi,j)n×nB = (b_{i,j})_{n \times n}，其中bi,j=1b_{i, j} = 1表示ii可以直接或间接到达jj，bi,j=0b_{i, j} = 0表示ii无法直接或间接到达jj

样例输入

4
0 0 0 1
1 0 0 0
0 0 0 1
0 1 0 0
Copy

样例输出

1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
Copy

信息

ID
1028
难度
1
分类
图结构 | 平面图 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

模板 | Templates

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. Language
  1. © 2024 oj.xzynb.top
  2. Powered by AKIOIOJ and Vijos