用c语言编写程序,通过输入一个简单有向图的邻接矩阵,输出其强分图的邻接矩阵

好的，我可以帮您回答这个问题。下面是C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100  // 最大顶点数

int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
int visited[MAX_VERTEX_NUM];  // 记录节点是否被访问过

int n;  // 图的节点数

// 深度优先遍历
void DFS(int v)
{
    visited[v] = 1;  // 标记节点v已被访问

    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {  // 如果节点v与节点i之间有边且节点i未访问
            DFS(i);
        }
    }
}

// 反向图的邻接矩阵
void reverseGraph(int reverse_graph[][MAX_VERTEX_NUM])
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            reverse_graph[i][j] = graph[j][i];  // 反向边
        }
    }
}

// 判断是否强连通
int isStronglyConnected()
{
    int reverse_graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 反向图的邻接矩阵

    reverseGraph(reverse_graph);  // 构建反向图

    // 从节点0开始深度优先遍历
    DFS(0);

    // 如果所有节点都能被访问到，则原图强连通
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            return 0;
        }
    }

    // 重置visited数组
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    // 从反向图的节点0开始深度优先遍历
    DFS(0);

    // 如果所有节点都能被访问到，则反向图强连通
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            return 0;
        }
    }

    return 1;
}

// 输出强分图的邻接矩阵
void outputStronglyConnectedGraph()
{
    int strongly_connected_graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 强分图的邻接矩阵

    // 构建强分图的邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (visited[i] && visited[j] && graph[i][j]) {  // 如果节点i和节点j在同一个强连通分量中且节点i和节点j之间有边
                strongly_connected_graph[i][j] = 1;
            } else {
                strongly_connected_graph[i][j] = 0;
            }
        }
    }

    // 输出强分图的邻接矩阵
    printf("强分图的邻接矩阵：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", strongly_connected_graph[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    // 输入有向图的邻接矩阵
    printf("请输入有向图的邻接矩阵：\n");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // 判断是否强连通
    if (!isStronglyConnected()) {
        printf("该有向图不是强连通图！\n");
        return 0;
    }

    // 输出强分图的邻接矩阵
    outputStronglyConnectedGraph();

    return 0;
}

希望能够帮助到您！