输入格式: 首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试第一行输入2个整数n、m(2≤n≤26,1≤m≤n(n-1)/2),分别表示顶点数、边数;然后输入m行,每行包含两个顶点Ai、Bi(大写字母表示),表示Ai到Bi有一条有向边。 输出格式: 对于每组测试,输出n行,依顶点的字典序在每行上输出各顶点的入度和出度(数据之间留一个空格)。
时间: 2024-02-18 15:04:27 浏览: 135
ff.rar_grahamscan_n个点求其凸包_凸包测试数据_求其凸包。
好的,针对您的问题,我可以帮您解答。
输入格式:
首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试第一行输入2个整数n、m(2≤n≤26,1≤m≤n(n-1)/2),分别表示顶点数、边数;然后输入m行,每行包含两个顶点Ai、Bi(大写字母表示),表示Ai到Bi有一条有向边。
输出格式:
对于每组测试,输出n行,依顶点的字典序在每行上输出各顶点的入度和出度(数据之间留一个空格)。
算法思路:
为了方便处理字典序,我们可以将顶点用数字表示,即 A 表示为 1,B 表示为 2,以此类推。然后用邻接矩阵或邻接表存储有向图,统计每个顶点的入度和出度,最后按字典序输出即可。
具体实现:
下面给出基于邻接表的实现代码,您可以参考一下:
```python
# 定义一个转换函数,将大写字母转换为对应的数字
def trans(ch: str) -> int:
return ord(ch) - ord('A') + 1
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
# 初始化邻接表
adj = [[] for _ in range(n+1)]
# 统计入度、出度
in_degree = [0] * (n+1)
out_degree = [0] * (n+1)
for i in range(m):
a, b = map(str, input().split())
u, v = trans(a), trans(b)
adj[u].append(v) # 添加边
out_degree[u] += 1 # 统计出度
in_degree[v] += 1 # 统计入度
# 按字典序输出结果
for i in range(1, n+1):
ch = chr(ord('A') + i - 1)
print(ch, end=' ')
print(in_degree[i], out_degree[i])
```
希望以上代码和解释能够帮到您,如果您还有其他问题,可以继续问我哦。
阅读全文