1 图的定义和相关术语 2题

sy374: 无向图的度 简单

https://sunnywhy.com/sfbj/10/1/374

现有一个共n个顶点、m条边的无向图（假设顶点编号为从0到n-1），求每个顶点的度。

输入

第一行两个整数n、m（$1\le n\le 100,0\le m\le \frac{n(n-1)}{2}$），分别表示顶点数和边数；

接下来m行，每行两个整数u、v（$0\le u\le n-1,0\le v\le n-1,u\ne v$），表示一条边的两个端点的编号。数据保证不会有重边。

输出

在一行中输出n个整数，表示编号为从0到n-1的顶点的度。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 2
0 1
0 2

输出

2 1 1

解释

对应的无向图如下图所示，0号顶点的度为2，1号和2号顶点的度为1。

为了求解每个顶点的度，我们可以创建一个列表来存储每个顶点的度，初始值都为0。然后，对于每条边，我们将边的两个端点的度都加1。

以下是实现这个过程的Python代码：

n, m = map(int, input().split())
degrees = [0] * n
for _ in range(m):
    u, v = map(int, input().split())
    degrees[u] += 1
    degrees[v] += 1

print(' '.join(map(str, degrees)))

这段代码首先读取输入，然后创建一个列表来存储每个顶点的度。然后，它遍历每条边，将边的两个端点的度都加1。最后，它输出每个顶点的度。

sy375: 有向图的度 简单

https://sunnywhy.com/sfbj/10/1/375

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1），求每个顶点的入度和出度。

输入

第一行两个整数n、m（$1\le n\le 100,0\le m\le n(n-1)$），分别表示顶点数和边数；

接下来m行，每行两个整数u、v（$0\le u\le n-1,0\le v\le n-1,u\ne v$），表示一条边的两个端点的编号。数据保证不会有重边。

输出

输出行，每行为编号从0到n-1的一个顶点的入度和出度，中间用空格隔开。

样例1

输入

3 3
0 1
0 2
2 1

输出

0 2
2 0
1 1

解释

对应的有向图如下图所示。

0号顶点有0条入边，2条出边，因此入度为0，出度为2；

1号顶点有2条入边，0条出边，因此入度为2，出度为0；

2号顶点有1条入边，1条出边，因此入度为1，出度为1。

为了求解每个顶点的入度和出度，我们可以创建两个列表来分别存储每个顶点的入度和出度，初始值都为0。然后，对于每条边，我们将起点的出度加1，终点的入度加1。

以下是实现这个过程的Python代码：

n, m = map(int, input().split())
in_degrees = [0] * n
out_degrees = [0] * n
for _ in range(m):
    u, v = map(int, input().split())
    out_degrees[u] += 1
    in_degrees[v] += 1

for i in range(n):
    print(in_degrees[i], out_degrees[i])

这段代码首先读取输入，然后创建两个列表来存储每个顶点的入度和出度。然后，它遍历每条边，将边的起点的出度加1，终点的入度加1。最后，它输出每个顶点的入度和出度。