树的存储(Storing a Tree)

题目描述

要想对一棵树进行搜索，首先要解决存储的问题。这里我们学习一种最简单的存储方式——邻接矩阵：用一个二维数组 a 记录每一对节点之间是否有边相连。

• 如果节点 u 和节点 v 之间有一条边，就令 a[u][v] = 1；
• 如果没有边，就令 a[u][v] = 0。

因为树是无向的（既可以从上往下走，也可以从下往上走），所以每条边 u-v 要在矩阵中记录两个位置：a[u][v] = 1 且 a[v][u] = 1。这样得到的邻接矩阵关于主对角线（左上角到右下角）对称。

现在有一棵 n 个节点、m 条边的树（树中 m = n - 1），已知每条边连接的两个节点编号。请你把这棵树存入邻接矩阵，并把矩阵打印出来。

输入格式

第一行两个整数 n 和 m，分别表示节点个数和边的条数。

接下来 m 行，每行两个整数 u 和 v，表示节点 u 和节点 v 之间有一条边。

输出格式

输出一个 n 行 n 列的邻接矩阵：

• 每一行的 n 个数字之间用一个空格隔开；
• 有边的位置输出 1，没有边的位置输出 0；
• 矩阵关于主对角线对称。

样例输入

7 6
1 2
1 3
2 4
2 5
4 6
4 7

样例输出

0 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 0 0 0
0 1 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0

数据范围

• 1 ≤ n ≤ 1000
• m = n - 1
• 1 ≤ u, v ≤ n，保证输入构成一棵树

提示

读入每条边 u v 后，同时做两个赋值：a[u][v] = 1; a[v][u] = 1;，最后按行打印矩阵即可。注意最后一个数字后面不要多输出空格。