28 lines
747 B
C++
28 lines
747 B
C++
// B3611：至少经过一条边的可达性，不预先把对角线设为 true。
|
|
#include <iostream>
|
|
using namespace std;
|
|
bool reach[105][105]{};
|
|
|
|
void closure(int n) {
|
|
for (int k = 1; k <= n; ++k)
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = 1; j <= n; ++j)
|
|
reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
int n, x;
|
|
cin >> n;
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = 1; j <= n; ++j) {
|
|
cin >> x;
|
|
reach[i][j] = (x != 0);
|
|
}
|
|
closure(n);
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = 1; j <= n; ++j)
|
|
cout << int(reach[i][j]) << (j == n ? '\n' : ' ');
|
|
}
|