Convert a digraph to the corresponding undirected graph in linear time using adjacency lists

Question

Suppose we have a directed graph $G = (V,E$) represented with adjacency lists. Is it possible to convert $G$ into its undirected equivalent* $G'$, also represented with adjacency lists, in $O(|V|+|E|)$ time?

The obvious algorithm walks the adjacency list of each vertex $v$, and for each adjacent vertex $u$, inserts edges $(v,u)$ and $(u,v)$ into $G'$. The issue is duplicates. If $(u,v)$ happens to be in $G$ already, $(u,v)$ will be inserted into $G'$ twice: once when processing $v$'s adjacency list, and once when processing $u$'s. Assuming that a well-formed graph doesn't contain any duplicate edges, we would need to check $u$'s adjacency list to see whether it contains $v$ before performing the second insertion. But this check takes linear time in $|V|$, and we would need to perform this check for $O(|E|)$ edges, resulting in $O(|V|*|E|)$ time complexity.

*Terminology: by "undirected equivalent" of a digraph $G=(V,E)$, I mean the directed graph $G'=(V,E')$ such that

if $(v,u) \in E$ then $(v,u) \in E'$ and $(u,v) \in E'$ and
if $(v,u) \in E'$ then either $(v,u) \in E$ or $(u,v) \in E$.

Answer 1

If you perform the check at the end rather than throughout, it will be much faster.

Start by going over all edges, and for each edge $(i,j)$ add the edge $(j,i)$ to the adjacency list of $j$.

Now given the adjacency list of $i$, we want to remove duplicates. For that we use an array indexed by $V$, which is initialized to zero (we only need to initialize it once). Go over the list and count how many times you see each edge. Now go over the list a second time and only add the first occurrence of every edge. Finally, go over the list a third time to reset the array back to zero. In all, we do $O(1)$ work per edge.

One drawback of this algorithm is that the resulting adjacency lists aren't sorted, even if you started out with sorted ones. Here is a different algorithm which works in $O(|V|+|E|)$ time and maintains this invariant (assuming it holds originally). For each vertex $i$, compute the sorted lists $\{ j : (i,j) \in G \}$ and $\{ j : (j,i) \in G \}$. Then merge them and remove duplicates.

Answer 2

Yuval's idea is probably better, but I'm posting mine anyway since it's a different approach.

First of all, observe that the only duplicates are those involving two nodes $u, v$ such that there is an edge "in both directions", in other words cycles of length two.

In the DFS forest of $G$, the only such edges are back-edges going from a node to its parent. This suggests an algorithm to solve your problem. Perform a DFS of $G$, adding each edge you find to $G'$, except for the edges $(u, v)$ such that $v = \pi(u)$.