图论的存储

在图论中，根据图的类型（稀疏或稠密）、方向性（有向或无向）、是否加权等特点，选择合适的存储方式至关重要。下面详细介绍使用 C++ STL 容器 vector 实现两种主要的图存储方法：邻接矩阵和邻接表，并探讨如何优化这些方法，尤其适用于笔试编程和高效算法的实现。

前置知识

• 稀疏图：边的数量远小于顶点数的平方。
• 稠密图：边的数量接近顶点数的平方。
• 有向图：边具有方向性。
• 无向图：边没有方向，可以视作双向边。
• 有权图与无权图：有权图的边具有权值，无权图的边没有权值。

题目描述：

给定两张有向图 $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 \leq n \leq 10^3$
  • 图 $A$ 的邻接矩阵大小为 $n \times 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"。