从输入构建邻接表
构建竞赛题目所给出的图
从输入构建邻接表 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
图究竟是什么
图就是由称为节点的点和称为边的线组成的结构。由道路连接起来的城市就是您已经熟悉的一种图。🗺️
节点与边
每个节点代表一个事物，每条边表示两个节点相互连接。竞赛中的图通常将节点编号为 1 到 n。
邻接表
竞赛中最常用的存储方式是邻接表：为每个节点保存一个直接邻居的列表。
adj = [[] for _ in range(n + 1)]为什么不用矩阵
矩阵需要 n 的平方级内存，在 n 很大时会急剧膨胀。邻接表只存储实际存在的边，因此更具扩展性。
读取第一行
大多数输入以两个数字开头：n 个节点和 m 条边。先读取它们，这样您就知道需要读取多少条边。
n, m = map(int, input().split())每行一条边
接下来的 m 行中，每行给出一对 u v。这条边表示 u 和 v 直接相连。
u, v = map(int, input().split())无向表示两个方向
对于无向边，请在两个方向都添加连接。您既可以从 u 走到 v，也可以从 v 走到 u。
adj[u].append(v)
adj[v].append(u)有向表示单向
对于有向边，只存储从 u 到 v 的连接。请仔细阅读题目描述，确认您处理的是哪一种边。
adj[u].append(v)在循环中构建
循环 m 次，读取每一对节点，并填充列表。循环结束后，您的邻接表就包含了整个图。
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)从 1 开始的索引与从 0 开始的索引
如果节点从 1 开始编号，请将列表大小设为 n 加 1，这样索引 n 才有效。弄混索引方式会导致不易察觉的错误。
访问节点的邻居
构建完成后，探索就很简单了：遍历某个节点的邻接表，一步即可到达每个邻居。
for nb in adj[u]:
print(nb)快速检查
您读取到了一条无向边 u v。应该存储什么？
回顾
现在您可以使用邻接表构建图：读取 n 和 m，遍历各条边，并在无向图中添加两个方向的连接。🎉
常见问题解答
「从输入构建邻接表」课时是免费的吗？
是的 — 「从输入构建邻接表」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「从输入构建邻接表」这节课中我会学到什么？
构建竞赛题目所给出的图 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「从输入构建邻接表」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。