在pta中利用c语言完成下述问题：求有向图G中各顶点的入度与出度。建议分别采用邻接矩阵和邻接表这两种不同的存储结构完成。 输入格式: 首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试第一行输入2个整数n、m（2≤n≤26，1≤m≤n(n-1)/2），分别表示顶点数、边数；然后输入m行，每行包含两个顶点Ai、Bi（大写字母表示），表示Ai到Bi有一条有向边。 输出格式: 对于每组测试，输出n行，依顶点的字典序在每行上输出各顶点的入度和出度（数据之间留一个空格）。 输入样例: 1 5 4 A C A B B D E C 输出样例: 0 2 1 1 2 0 1 0 0 1 来源： [1] 黄龙军, 等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881 [2] 黄龙军, 等. 数据结构与算法（Python版）,上海: 上海交通大学出版社, 2023. （In Press） 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

算法1

(邻接矩阵) $O(n^2)$

对于邻接矩阵来说，我们只需要遍历整个矩阵，计算出每个顶点的入度和出度即可。

时间复杂度

参考文献

C++ 代码

算法2

(邻接表) $O(m)$

对于邻接表来说，我们需要先建立图，然后遍历每个顶点的边表，计算出每个顶点的入度和出度。

时间复杂度

参考文献

C++ 代码

相关问题

用c语言写求有向图中每个顶点的入度和出度的程序并用文字说明其储存结构和算法设计

好的，我会为您解答。首先，对于有向图中每个顶点的入度和出度，我们可以通过遍历图的所有边，统计每个顶点的入度和出度来实现。具体来说，我们可以采用邻接矩阵或邻接表来存储有向图。

邻接矩阵是一个二维数组，其中每个元素表示一条边的权重。对于有向图，如果从顶点i到顶点j存在一条边，则邻接矩阵的第i行第j列的元素为1；否则为0。因此，我们可以通过遍历邻接矩阵的每一行或每一列来计算每个顶点的出度或入度。

邻接表则是由每个顶点的出边链表组成的数组。每个链表中的元素表示从该顶点出发的一条边。因此，我们可以通过遍历每个顶点的出边链表来计算该顶点的出度，遍历每个顶点的入边链表来计算该顶点的入度。

下面是一个使用邻接矩阵的C语言程序，用于计算有向图的每个顶点的入度和出度：

#include <stdio.h>

#define MAX_VERTEX_NUM 100

typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num, edge_num; // 顶点数和边数
} Graph;

void init_graph(Graph* g, int vertex_num) {
    g->vertex_num = vertex_num;
    g->edge_num = 0;
    for (int i = 0; i < vertex_num; ++i) {
        for (int j = 0; j < vertex_num; ++j) {
            g->edges[i][j] = 0; // 初始化邻接矩阵
        }
    }
}

void add_edge(Graph* g, int from, int to) {
    g->edges[from][to] = 1; // 添加一条边
    ++g->edge_num;
}

void calculate_degree(const Graph* g, int vertex) {
    int in_degree = 0, out_degree = 0;
    for (int i = 0; i < g->vertex_num; ++i) {
        if (g->edges[vertex][i] == 1) { // 出度
            ++out_degree;
        }
        if (g->edges[i][vertex] == 1) { // 入度
            ++in_degree;
        }
    }
    printf("Vertex %d: in-degree = %d, out-degree = %d\n", vertex, in_degree, out_degree);
}

int main() {
    Graph g;
    int vertex_num = 5;
    init_graph(&g, vertex_num);
    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 2);
    add_edge(&g, 1, 3);
    add_edge(&g, 2, 3);
    add_edge(&g, 3, 4);
    for (int i = 0; i < vertex_num; ++i) { // 计算每个顶点的入度和出度
        calculate_degree(&g, i);
    }
    return 0;
}

在这个程序中，我们通过邻接矩阵来存储有向图，并使用add_edge函数来添加边。在calculate_degree函数中，我们遍历邻接矩阵的每一行和每一列，分别计算每个顶点的入度和出度。最后，我们在main函数中遍历每个顶点，调用calculate_degree函数来计算它的入度和出度。

当然，如果我们使用邻接表来存储有向图，我们的程序也会有一些不同。不过，基本的思路是一样的，我们仍然需要遍历每个顶点的出边链表或入边链表来计算入度和出度。

希望这个回答能够帮助您理解如何用C语言编写求有向图中每个顶点的入度和出度的程序，并且了解其储存结构和算法设计。

编写类c代码求出邻接表表示的有向图中序号为numb的顶点的入度和出度

好的，这是一个技术问题，我可以回答。对于邻接表表示的有向图，我们可以通过遍历中序号为numb的顶点的边来计算出该顶点的入度和出度。具体方法如下：

1. 遍历整个邻接表，找到以该顶点为起点的所有有向边，累加出度。

2. 遍历整个邻接表，找到以该顶点为终点的所有有向边，累加入度。

通过这种方法，我们就可以在时间复杂度为O(E)的情况下求出该顶点的入度和出度，其中E为边的数量。