P3994.图的读入与构建
题目描述:
给定两张有向图 A 和 B,其中图 A 以邻接矩阵形式给出,图 B 以邻接表形式给出。请判断这两张图是否完全一样。我们将“完全一样”的定义为:每个节点的邻居集合完全一致。
输入
输入的第一行包含两个整数 n,表示图的节点数。
接下来的n行,给出图 A 的邻接矩阵。该矩阵的第 i 行第 j 列表示节点 i 和节点 j 之间是否有边。如果存在边,则该位置的值为 1,否则为 0。
接下来的n行,给出图 B 的邻接表。每行第一个数node,后面跟的第一个数k表示接下来输入k个数val表示节点node向这些节点val连一条边
输出
如果图 A 和图 B 完全一样,则输出 "YES";否则输出 "NO"。
注意
- 图 A 和图 B 是有向图,即如果 A[i][j]=1,那么 i 到 j 有条有向边。
- 节点编号从 1 到 n。
- 图 A 和图 B 的节点数相同。
- 数据范围:
- 1≤n≤103
- 图 A 的邻接矩阵大小为 n×n,其中每个元素为 0 或 1。
- 图 B 的邻接表中每个节点的邻居数量不超过 n−1。
样例输入 1
3
0 1 1
1 0 1
1 1 0
1 2 2 3
2 2 1 3
3 2 1 2
样例输出 1
YES
样例输入 2
3
0 1 1
1 0 1
1 1 0
1 2 2 3
2 2 1 3
3 1 1
样例输出 2
NO
样例2提示
图 A 的邻接矩阵为:
0 1 1
1 0 1
1 1 0
表示图 A 中,节点 1 与节点 2 和节点 3 相连,节点 2 与节点 1 和节点 3 相连,节点 3 与节点 1 和节点 2 相连。
图 B 的邻接表为:
1 2 2 3
2 2 1 3
3 1 1
表示图 B 中,节点 1 与节点 2 和节点 3 相连,节点 2 与节点 1 和节点 3 相连,节点 3 与节点 1 相连。
对比可以发现,在图 B 中,节点 3 不连向 节点 2。因此,图 A 和图 B 不完全一样,输出 "NO"。