1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

图论的存储

图的存储方式对于算法的效率和实现的简便性有着直接影响。本文介绍了两种常见的图的存储方法:邻接矩阵和邻接表,并提供了使用 Python 实现这两种方法的详细步骤。

前置知识

  • 稀疏图:边数远小于顶点数的平方的图。
  • 稠密图:边数接近顶点数的平方的图。
  • 有向图与无向图:有向图的边具有方向性,无向图的边可视为双向的。
  • 有权图与无权图:有权图的边具有权重,无权图的边没有权重。

P3994.图的读入与构建

    1000ms Tried: 1843 Accepted: 721 Difficulty: 5 所属公司 : Hot100
    算法与标签>模拟

题目描述:

给定两张有向图 AAA 和 BBB,其中图 AAA 以邻接矩阵形式给出,图 BBB 以邻接表形式给出。请判断这两张图是否完全一样。我们将“完全一样”的定义为:每个节点的邻居集合完全一致。

输入

输入的第一行包含两个整数 nnn,表示图的节点数。

接下来的nnn行,给出图 AAA 的邻接矩阵。该矩阵的第 iii 行第 jjj 列表示节点 iii 和节点 jjj 之间是否有边。如果存在边,则该位置的值为 1,否则为 0。

接下来的nnn行,给出图 BBB 的邻接表。每行第一个数nodenodenode,后面跟的第一个数kkk表示接下来输入kkk个数valvalval表示节点nodenodenode向这些节点valvalval连一条边

输出

如果图 AAA 和图 BBB 完全一样,则输出 "YES";否则输出 "NO"。

注意

  • 图 AAA 和图 BBB 是有向图,即如果 A[i][j]=1A[i][j] = 1A[i][j]=1,那么 iii 到 jjj 有条有向边。
  • 节点编号从 1 到 nnn。
  • 图 AAA 和图 BBB 的节点数相同。
  • 数据范围:
    • 1≤n≤1031 \leq n \leq 10^31≤n≤103
    • 图 AAA 的邻接矩阵大小为 n×nn \times nn×n,其中每个元素为 0 或 1。
    • 图 BBB 的邻接表中每个节点的邻居数量不超过 n−1n-1n−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提示

图 AAA 的邻接矩阵为:

0 1 1
1 0 1
1 1 0

表示图 AAA 中,节点 111 与节点 222 和节点 333 相连,节点 222 与节点 111 和节点 333 相连,节点 333 与节点 111 和节点 222 相连。

图 BBB 的邻接表为:

1 2 2 3
2 2 1 3
3 1 1

表示图 BBB 中,节点 111 与节点 222 和节点 333 相连,节点 222 与节点 111 和节点 333 相连,节点 333 与节点 111 相连。

对比可以发现,在图 BBB 中,节点 333 不连向 节点 222。因此,图 AAA 和图 BBB 不完全一样,输出 "NO"。

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 36ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?