- BC20280018's blog
传递闭包模板
- 2025-9-14 11:59:32 @
传递闭包模板
题目描述
给定一张点数为 的有向图的邻接矩阵,图中不包含自环,求该有向图的传递闭包。
一张图的邻接矩阵定义为一个 的矩阵 ,其中
$$ a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right. $$一张图的传递闭包定义为一个 的矩阵 ,其中
$$ b_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right. $$输入格式
输入数据共 行。
第一行一个正整数 。
第 到 行每行 个整数,第 行第 列的整数为 。
输出格式
输出数据共 行。
第 到 行每行 个整数,第 行第 列的整数为 。
输入输出样例 #1
输入 #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
说明/提示
对于 的数据,,保证 且 。
#include <bits/stdc++.h>
using namespace std;
int f[105][105];
int n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
scanf("%d", &f[i][j]);
}
for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
f[i][j] = f[i][j] | (f[i][k] & f[k][j]);
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
printf("%d ", f[i][j]);
printf("\n");
}
}