引入

一个 $n$ 个点有向图的邻接矩阵 $A$ 是一个 $n$ 阶布尔矩阵,它的幂组成的序列具有周期性。

设 $k,d$ 是满足 $A^k=A^{k+d}$ 的最小正整数,则 $k$ 称为 $A$ 的幂敛指数(index),$d$ 称为 $A$ 的周期(period)。

对于如下邻接矩阵 $A$,其各次幂分别为

$$A^1 = \left[\begin{matrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{matrix}\right]$$

$$A^2 = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$$

$$A^3 = \left[ \begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right]$$

$$A^4 = \left[ \begin{array}{ccccc} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{array} \right]$$

$$A^5 = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$$

此时,$A^5 = A^2$,故 $k=2,d=3$。

思路

矩阵 $A$ 的周期等于在图上每个点经过一定步数所能到达的点的周期。根据 B. De Schutter and B. De Moor 的报告 On the sequence of consecutive powers of a matrix in a Boolean algebra,强连通图的周期是其包含的所有环长度的最大公约数,而一般图的周期是其所有强连通分量周期的最小公倍数。简单证明如下:

对于一个强连通分量,设其包含的所有环长度的最大公约数为 $d_0$,那么任意选取一点为起点,沿有向边循坏按 $1-d_0$ 标号,每个点都只会有唯一的标号。那么,经过无限步后,一个点能够到达的点集合一定是以 $d_0$ 为周期循环的。

那么,整张图的周期,显然就是每个强连通分量周期的最小公倍数。得到周期 $d$ 之后,幂敛指数 $k$ 可以较为轻松地计算求得。

算法实现

计算强连通分量使用 $\text{Tarjan}$ 算法可以获得 $\Theta(V+E)$ 的复杂度。

对于每个强连通分量,任取一个点作为根开始 $\text{DFS}$。过程中,一条两端深度分别为 $i,j$ 的非树边对答案的贡献 $d’=|i+1-j|$,代表着一个长度为 $d’$ 的环,或者一对长度差为 $d’$ 的环。找到所有的 $d’$,它们的最大公约数就是这个强连通分量的周期。

得到整张图的周期后,从 $p=0$ 开始,我们不断验证 $A^{2^p} = A^{2^p+d}$ 这一等式的合法性,每次将 $p+1$。$k$ 的范围为 $[2^{p-1},2^p]$,其中 $p$ 为等式第一次合法时的值。在这个区间内,直接二分查找使 $A^k=A^{k+d}$ 存在的最小值。因为 $d$ 比较大,确定 $k$ 的范围的第一次查找需要计算 $\Theta(\log d)$ 次矩阵乘法。使用 $\text{bitset}$ 优化矩阵乘法可以获得 $\Theta(n^3\log d/32)$ 的复杂度。

代码