7-5 入度与出度

求有向图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. ISBN: 9787313280732

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>
#include <string.h>

#define MAX 26

void calculate(int n, int m)
{
    char adg[m][2];
    int adj[MAX][MAX] = {0};
    int in[MAX] = {0};
    int out[MAX] = {0};

    for (int i = 0; i < m; i++)
    {
        scanf(" %c %c", &adg[i][0], &adg[i][1]);
        int u = adg[i][0] - 'A';
        int v = adg[i][1] - 'A';
        adj[u][v] = 1;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (adj[i][j])
            {
                out[i]++;
                in[j]++;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        printf("%d %d\n", in[i], out[i]);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        calculate(n, m);
    }
    return 0;
}