【模板】传递闭包

题意

由有向图邻接矩阵求任意两点是否可达。

思路

每一行可达集合编码成整数位集。若 i 能到 k，就把 k 的整行可达集合并入 i；这正是 Warshall 转移，但一次 OR 同时处理全部终点。

Python 知识

Python 大整数天然是可变长位集。
mask |= value << index 编码一行邻接矩阵。
右移与按位与逐位恢复输出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19import sys


input = sys.stdin.buffer.readline
n = int(input())
rows = []
for _ in range(n):
    mask = 0
    for index, value in enumerate(map(int, input().split())):
        mask |= value << index
    rows.append(mask)
for middle in range(n):
    middle_bit = 1 << middle
    middle_row = rows[middle]
    for start in range(n):
        if rows[start] & middle_bit:
            rows[start] |= middle_row
for mask in rows:
    print(*(mask >> index & 1 for index in range(n)))

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

进行 O(n^2) 次大整数 OR，空间 O(n^2) 位。

总结

布尔矩阵行可以压成整数，把最内层循环交给底层位运算。

【模板】传递闭包

目录

题意

思路

Python 知识

代码

复杂度

总结