给定多图的邻接表，在 O(|V|+|E|) 时间内计算等效（简单）无向图的邻接表
Given an adjacency list for multigraph, compute adjacency list for equivalent (simple) undirected graph in O(|V|+|E|) time
我们得到了多重图的邻接表 G = (V, E) 并且需要找到 O(V + E) 算法来计算等效（简单）无向图的邻接表。
我在另一个 post 中找到了以下解决方案（它是问题部分的一部分，因此我重新 post）：
"[H]拥有一个大小为|V|的数组，以标记adj[u]中至少遇到过一次的顶点，从而防止重复。在遍历每个adj[之前重置数组你]."
原谅我的无知，但我不确定这是怎么回事 O(|V| + |E|)。重置长度的成本是多少 |V|数组 |V|次？
谢谢。
您不需要实际重置数组。
假设数组存储int。顶点被标记为 iff mark[u] == v 其中 v 是当前顶点的索引或 id。
当您移动到下一个顶点时，v 的值会发生变化，并且数组中的所有条目都将计算为 false，而无需更改数组中的值。
我们得到了多重图的邻接表 G = (V, E) 并且需要找到 O(V + E) 算法来计算等效（简单）无向图的邻接表。
我在另一个 post 中找到了以下解决方案（它是问题部分的一部分，因此我重新 post）：
"[H]拥有一个大小为|V|的数组，以标记adj[u]中至少遇到过一次的顶点，从而防止重复。在遍历每个adj[之前重置数组你]."
原谅我的无知，但我不确定这是怎么回事 O(|V| + |E|)。重置长度的成本是多少 |V|数组 |V|次？
谢谢。
您不需要实际重置数组。
假设数组存储int。顶点被标记为 iff mark[u] == v 其中 v 是当前顶点的索引或 id。
当您移动到下一个顶点时，v 的值会发生变化，并且数组中的所有条目都将计算为 false，而无需更改数组中的值。