利用位运算加速有向图全源可达性

· · 算法·理论

每日一个小技巧系列。看省选中的表现，还是有很多人不知道这个的。

问题

给定一个有向图，对每一个有序点对 (u, v) 求出是否可以由 u 到达 v。

问题背景

经典的算法是 n 次 dfs。复杂度 O(nm)。

学术界认为这个问题是困难的，目前没有显著更优的解（降低 n 或 m 的指数）。

但是，除以字长（w）是容易的。

转化为 dp

我们敏锐地注意到一点：设 \text{vis}_u 是 u 点到其他所有点的可达性数组。而 v 是 u 的一条出边所连的点。v 所能到达的所有点 u 也能到达。反映在 \text{vis} 上就是 \text{vis}_u \gets \text{vis}_u \;\operatorname{bit\_or}\; \text{vis}_v。其中的“bit_or”指的是将两个数组中所有对应位置上的元素或起来构成一个新数组。

于是我们想到可能可以做 dp。

但是显然的，dp 需要考虑转移顺序。在一个一般图上，我们无法找到好的转移顺序。

转移顺序

解决方法很简单。

在图上的 dp，我们一般考虑按拓扑序转移。

一般图没有拓扑序，我们需要将它转化为 DAG。

然后就是套路的 tarjan 了。

具体来讲：同一个强联通分量内的点都可以互相抵达。于是我们用 tarjan 对原图缩点，然后在新图上跑拓扑排序，沿拓扑序逆序做我们刚刚的 dp。

解决了。

优化

我们刚刚的 dp 还是 O(nm) 的复杂度。我说的“除以字长”在哪里呢？

其实你只需用 bitset（或自己实现的压位容器）存储 \text{vis} 数组，在或的时候就能使得复杂度除以 w。

然后真的结束了。时间复杂度 O(\frac{nm}{w})，但是空间复杂度是 O(\frac{n^2}{8}) 的，可能需要进一步优化。