求有向图G中各顶点的入度与出度。建议分别采用邻接矩阵和邻接表这两种不同的存储结构完成。 输入格式: 首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试第一行输入2个整数n、m(2≤n≤26,1≤m≤n(n-1)/2),分别表示顶点数、边数;然后输入m行,每行包含两个顶点Ai、Bi(大写字母表示),表示Ai到Bi有一条有向边。 输出格式: 对于每组测试,输出n行,依顶点的字典序在每行上输出各顶点的入度和出度(数据之间留一个空格)。
时间: 2023-12-06 14:39:43 浏览: 56
邻接矩阵存储方式的代码实现:
```python
T = int(input())
for _ in range(T):
n, m = map(int, input().split())
# 初始化邻接矩阵
matrix = [[0] * n for _ in range(n)]
# 读入边
for _ in range(m):
a, b = input().split()
# a到b有一条有向边,邻接矩阵中matrix[a][b]加1
matrix[ord(a)-65][ord(b)-65] += 1
# 输出各顶点的入度和出度
for i in range(n):
# 计算第i个顶点的出度
out_degree = sum(matrix[i])
# 计算第i个顶点的入度
in_degree = sum(matrix[j][i] for j in range(n))
print(chr(i+65), in_degree, out_degree)
```
邻接表存储方式的代码实现:
```python
# 边的类
class Edge:
def __init__(self, to):
self.to = to
self.next = None
T = int(input())
for _ in range(T):
n, m = map(int, input().split())
# 初始化邻接表
adj = [None] * n
for i in range(n):
adj[i] = Edge(None)
# 读入边
for _ in range(m):
a, b = input().split()
# a到b有一条有向边,将边插入邻接表中
edge = Edge(ord(b)-65)
edge.next = adj[ord(a)-65].next
adj[ord(a)-65].next = edge
# 输出各顶点的入度和出度
for i in range(n):
# 计算第i个顶点的出度
out_degree = 0
edge = adj[i].next
while edge:
out_degree += 1
edge = edge.next
# 计算第i个顶点的入度
in_degree = 0
for j in range(n):
edge = adj[j].next
while edge:
if edge.to == i:
in_degree += 1
break
edge = edge.next
print(chr(i+65), in_degree, out_degree)
```