2 图的存储 4题

sy376: 无向图的邻接矩阵 简单

https://sunnywhy.com/sfbj/10/2/376

现有一个共n个顶点、m条边的无向图（假设顶点编号为从0到n-1），将其按邻接矩阵的方式存储（存在边的位置填充1，不存在边的位置填充0），然后输出整个邻接矩阵。

输入

第一行两个整数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行n列，表示邻接矩阵。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 2
0 1
0 2

输出

0 1 1
1 0 0
1 0 0

解释

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

0号顶点有2条出边，分别到达1号顶点和2号顶点；

1号顶点有1条出边，到达0号顶点；

2号顶点有1条出边，到达0号顶点。

为了将无向图按邻接矩阵的方式存储，我们可以创建一个n*n的二维列表，初始值都为0。然后，对于每条边，我们将边的两个端点对应的位置填充为1。

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

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

for row in adjacency_matrix:
    print(' '.join(map(str, row)))

这段代码首先读取输入，然后创建一个n*n的二维列表来存储邻接矩阵。然后，它遍历每条边，将边的两个端点对应的位置填充为1。最后，它输出整个邻接矩阵。

sy377: 有向图的邻接矩阵 简单

https://sunnywhy.com/sfbj/10/2/377

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1），将其按邻接矩阵的方式存储（存在边的位置填充1，不存在边的位置填充0），然后输出整个邻接矩阵。

输入

第一行两个整数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$），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

输出n行n列，表示邻接矩阵。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 3
0 1
0 2
2 1

输出

0 1 1
0 0 0
0 1 0

解释

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

0号顶点有2条出边，分别到达1号顶点和2号顶点；

1号顶点有0条出边；

2号顶点有1条出边，到达1号顶点。

为了将有向图按邻接矩阵的方式存储，我们可以创建一个n*n的二维列表，初始值都为0。然后，对于每条边，我们将边的起点和终点对应的位置填充为1。

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

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

for row in adjacency_matrix:
    print(' '.join(map(str, row)))

这段代码首先读取输入，然后创建一个n*n的二维列表来存储邻接矩阵。然后，它遍历每条边，将边的起点和终点对应的位置填充为1。最后，它输出整个邻接矩阵。

sy378: 无向图的邻接表 简单

https://sunnywhy.com/sfbj/10/2/378

现有一个共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$），表示一条边的两个端点的编号。数据保证不会有重边。

输出

输出行，按顺序给出编号从0到n-1的顶点的所有出边，每行格式如下：

id(k) v_1 v_2 ... v_k

其中id表示当前顶点的编号，k表示该顶点的出边数量，v1、v2、...、vk 表示k条出边的终点编号（按边输入的顺序输出）。行末不允许有多余的空格。

样例1

输入

3 2
0 1
0 2

输出

0(2) 1 2
1(1) 0
2(1) 0

解释

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

0号顶点有2条出边，分别到达1号顶点和2号顶点；

1号顶点有1条出边，到达0号顶点；

2号顶点有1条出边，到达0号顶点。

为了将无向图按邻接表的方式存储，我们可以创建一个列表，其中每个元素都是一个列表，表示一个顶点的所有邻接顶点。然后，对于每条边，我们将边的两个端点添加到对方的邻接列表中。

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

n, m = map(int, input().split())
adjacency_list = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adjacency_list[u].append(v)
    adjacency_list[v].append(u)

for i in range(n):
    num = len(adjacency_list[i])
    if num == 0:
        print(f"{i}({num})")
    else:
        print(f"{i}({num})", ' '.join(map(str, adjacency_list[i])))

这段代码首先读取输入，然后创建一个列表来存储邻接表。然后，它遍历每条边，将边的两个端点添加到对方的邻接列表中。最后，它输出整个邻接表。

sy379: 有向图的邻接表 简单

https://sunnywhy.com/sfbj/10/2/379

现有一个共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的顶点的所有出边，每行格式如下：

id(k) v_1 v_2 ... v_k

其中id表示当前顶点的编号，k表示该顶点的出边数量，v1、v2、...、vk表示k条出边的终点编号（按边输入的顺序输出）。行末不允许有多余的空格。

样例1

输入

3 3
0 1
0 2
2 1

输出

0(2) 1 2
1(0)
2(1) 1

解释

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

0号顶点有2条出边，分别到达1号顶点和2号顶点；

1号顶点有0条出边；

2号顶点有1条出边，到达1号顶点。

为了将有向图按邻接表的方式存储，我们可以创建一个列表，其中每个元素都是一个列表，表示一个顶点的所有邻接顶点。然后，对于每条边，我们将边的终点添加到起点的邻接列表中。

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

n, m = map(int, input().split())
adjacency_list = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adjacency_list[u].append(v)

for i in range(n):
    num = len(adjacency_list[i])
    if num == 0:
        print(f"{i}({num})")
    else:
        print(f"{i}({num})", ' '.join(map(str, adjacency_list[i])))

这段代码首先读取输入，然后创建一个列表来存储邻接表。然后，它遍历每条边，将边的终点添加到起点的邻接列表中。最后，它输出整个邻接表。