给定两张有向图 A 和 B,其中图 A 以邻接矩阵形式给出,图 B 以邻接表形式给出。请判断这两张图是否完全一样。我们将“完全一样”的定义为:每个节点的邻居集合完全一致。
输入的第一行包含两个整数 n,表示图的节点数。
接下来的n行,给出图 A 的邻接矩阵。该矩阵的第 i 行第 j 列表示节点 i 和节点 j 之间是否有边。如果存在边,则该位置的值为 1,否则为 0。
在图论中,根据图的类型(稀疏或稠密)、方向性(有向或无向)、是否加权等特点,选择合适的存储方式至关重要。下面详细介绍使用 C++ STL 容器 vector
实现两种主要的图存储方法:邻接矩阵和邻接表,并探讨如何优化这些方法,尤其适用于笔试编程和高效算法的实现。