传递闭包模板


题目描述

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

一张图的邻接矩阵定义为一个 n×nn\times n 的矩阵 A=(aij)n×nA=(a_{ij})_{n\times n},其中

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

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

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

输入格式

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

第一行一个正整数 nn

22n+1n+1 行每行 nn 个整数,第 i+1i+1 行第 jj 列的整数为 aija_{ij}

输出格式

输出数据共 nn 行。

11nn 行每行 nn 个整数,第 ii 行第 jj 列的整数为 bijb_{ij}

输入输出样例 #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

说明/提示

对于 100%100\% 的数据,1n1001\le n\le 100,保证 aij{0,1}a_{ij}\in\{0,1\}aii=0a_{ii}=0


#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");
	}
}