algorithm - 在 O(m) 时间内使用非邻接表检查图的连通性

Question

问题如下：

我们仍然知道一个数字 n，表示图中的节点数。然而，我们得到的不是图的邻接表，而是一个排序好的“非邻接表”。非邻接链表是指节点与链表上的节点之间不存在边，如果节点对不在链表上，则存在边。例如，如果节点 3 的排序链表是 1 -> 2 -> 10 -> NULL，则表示对之间没有边：(3,1),(3,2) 和 (3, 10)，但所有其他 (3, j) 对都存在。假设非邻接表共有m个元素且m>n，设计一个算法检查给定图是否在O(m)时间内连通。

通常这将是小菜一碟，只需修改 DFS 并运行以查看它是否已连接。但是 O(m) 部分让我绊倒了。我一直在尝试降低时间复杂度，但我一直坚持如何将其降低到 O(m)。

标签： algorithmgraphtime-complexitybig-odepth-first-search