用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 stack[MAX_VERTEX_NUM];  // 栈，用于记录遍历的节点
int top = -1;  // 栈顶指针

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);
        }
    }

    // 将节点v入栈
    stack[++top] = v;
}

// 反向图的邻接矩阵
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];  // 反向边
        }
    }
}

// 求强连通分量
void getStronglyConnectedComponent(int v, int scc[], int *size)
{
    visited[v] = 1;  // 标记节点v已被访问

    scc[(*size)++] = v;  // 将节点v加入当前强连通分量

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

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

    // 构建强分图的邻接矩阵
    for (int i = 0; i < scc_count; i++) {
        for (int j = 0; j < scc_list[i][MAX_VERTEX_NUM - 1]; j++) {
            int u = scc_list[i][j];
            for (int k = 0; k < n; k++) {
                if (graph[u][k] && scc_list[i][MAX_VERTEX_NUM - 2]) {  // 如果节点u和节点k之间有边且节点k在其他强连通分量中
                    for (int l = 0; l < scc_count; l++) {
                        if (l == i) {  // 如果是同一个强连通分量，则不需要处理
                            continue;
                        }
                        for (int m = 0; m < scc_list[l][MAX_VERTEX_NUM - 1]; m++) {
                            int v = scc_list[l][m];
                            if (v == k) {  // 如果节点v在其他强连通分量中且与节点k之间有边，则在强分图中加入边(u, v)
                                strongly_connected_graph[u][v] = 1;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    // 输出强分图的邻接矩阵
    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]);
        }
    }

    // 构建反向图
    int reverse_graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 反向图的邻接矩阵
    reverseGraph(reverse_graph);

    // 第一遍深度优先遍历
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS(i);
        }
    }

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

    // 求强连通分量
    int scc[MAX_VERTEX_NUM];  // 当前强连通分量
    int scc_list[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 强连通分量列表
    int scc_count = 0;  // 强连通分量数量
    while (top >= 0) {
        int v = stack[top--];
        if (!visited[v]) {
            int size = 0;
            getStronglyConnectedComponent(v, scc, &size);
            for (int i = 0; i < size; i++) {
                visited[scc[i]] = 1;
            }
            scc[MAX_VERTEX_NUM - 1] = size;  // 记录当前强连通分量的大小
            for (int i = 0; i < size; i++) {
                scc_list[scc_count][i] = scc[i];
            }
            scc_list[scc_count++][MAX_VERTEX_NUM - 1] = size;  // 记录当前强连通分量的大小
        }
    }

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

    return 0;
}

希望能够帮助到您！