Question

无向图用矩阵幂算法如何求其连通分支数

Answer 1

设连通矩阵A,x->y若连通,则A[x][y]=1（当然也有A[y][x]=1）,否则A[x][y]=0,特别地有A[x][x]=1

此时A[x][y]>0当且仅当x->y有直接连通的边

再考虑A^2=A*A,A^2[x][y]>0当且仅当x->y有长度小于等于2条边的通路

最后,A^n[x][y]>0当且仅当x->y有任意长度的通路（n是节点数目）

所以用快速幂求出A^n,然后将A^n作为邻接矩阵,DFS一遍就可以了