蓝桥杯--关联矩阵

试题 算法训练 关联矩阵

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

 有一个n个结点m条边的有向图，请输出他的关联矩阵。

输入格式

 第一行两个整数n、m，表示图中结点和边的数目。n<=100,m<=1000。

 接下来m行，每行两个整数a、b，表示图中有(a,b)边。

 注意图中可能含有重边，但不会有自环。

输出格式

 输出该图的关联矩阵，注意请勿改变边和结点的顺序。

样例输入

5 9

1 2

3 1

1 5

2 5

2 3

2 3

3 2

4 3

5 4

样例输出

1 -1 1 0 0 0 0 0 0

-1 0 0 1 1 1 -1 0 0

0 1 0 0 -1 -1 1 -1 0

0 0 0 0 0 0 0 1 -1

0 0 -1 -1 0 0 0 0 1

观察样例可知 每列都只有一个1和-1，1对应的节点就是出节点，-1对应的是入节点

因此建立矩阵，我们只需要每列依次填入1和-1即可

注意要用字符串来做，因为用数字到最后输出的时候往往因为格式不对而不通过

n,m = map(int,input().split())
num_list = [[' 0']*m for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    # 重点 ，不能用数字
    num_list[a-1][i] = ' 1'
    num_list[b-1][i] = '-1'
for i in range(len(num_list)):
    for j in range(len(num_list[i])):
        print(num_list[i][j],end='')
    print()

样例输出容易误导人，其实输出应该是标准的矩形

1-1 1 0 0 0 0 0 0

-1 0 0 1 1 1-1 0 0

0 1 0 0-1-1 1-1 0

0 0 0 0 0 0 0 1-1

0 0-1-1 0 0 0 0 1