graph - 有趣的 Python 数据结构问题，涉及不相交集、散列和图

Question

问题：你正计划和你的两个最好的朋友在夏天进行一次环球旅行。你们三个想去的城市总共有 n 个。当您环游世界时，您会担心时区和机场访问。因此，有些城市只能在访问另一个城市之后才能访问，该城市位于附近的时区或有机场，它们表示为一对（cityX，cityY）的列表（cityX只能在访问cityY后访问）。给定城市总数和依赖对列表，你们是否可以访问所有城市？你的任务是编写函数 can_visit_all_cities，它决定在给定依赖关系的情况下是否可以访问 n 个城市。要求 • 必须在 O(m+n) 中运行，并且不能使用内置 Python 集/字典

标签： graphhashdepth-first-searchbreadth-first-searchdisjoint-sets

Answer 1

这听起来像一个依赖图。我不知道 python 是否有一个内置的数据结构。

如果您要自己实现一个，则必须使用列表/集合。