判断有向图是否为强连通图

在离散数学中，强连通图是一种特殊的有向图，其中任意两个顶点之间都存在从起点到终点的路径。判断一个有向图是否为强连通图是离散数学中的一个重要问题。本篇文章将介绍如何利用邻接矩阵来判断有向图是否为强连通图，并解释可达矩阵的计算方法。

首先，我们需要了解邻接矩阵和可达矩阵的概念。邻接矩阵是一种表示图的方法，其中矩阵的行和列都对应图的顶点，如果从顶点i到顶点j有一条边，则矩阵的第i行第j列的元素为1，否则为0。可达矩阵则表示从一个顶点到另一个顶点是否存在路径，可以通过Warshall算法计算得到。

接下来，我们可以通过以下步骤来判断一个有向图是否为强连通图：

1. 初始化邻接矩阵mapp和可达矩阵p，将mapp中的所有元素设为0，将p中的所有元素设为inf（表示不可达）。
2. 对于每个顶点i，将其对应的p[i][i]设为0（表示顶点i可达自己）。
3. 对于每个顶点i，遍历其邻接点j，如果mapp[i][j]为1（表示从顶点i到顶点j有一条边），则将p[i][j]设为0（表示从顶点i可以到达顶点j）。
4. 对于每个顶点i，遍历其邻接点j，如果p[i][j]仍为inf，则说明存在无法从顶点i到达顶点j的路径，即该有向图不是强连通图。
5. 如果所有顶点的可达性都已经确定，即所有的p[i][j]都已经不是inf，则说明该有向图是强连通图。

下面是一个示例代码，演示如何利用邻接矩阵判断有向图是否为强连通图：

#include <iostream>
#include <cstring>
using namespace std;
#define Max 1001
#define ll long long
#define inf 0x3f3f3f3f
int mapp[Max][Max], p[Max][Max];
int n, m;
void Warshall(int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mapp[i][k] == 1 && mapp[k][j] == 1) {
                    p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
                }
            }
        }
    }
}
int main() {
    memset(mapp, 0, sizeof(mapp));
    memset(p, inf, sizeof(p));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;\n