Algorithm to find a subgraph such that all of its edges has an anti edge

Question

Let $G=(V,E)$ be a directed graph. The "invertible" part of $G$ is the subgraph $H=(V,E_2)$ such that $(u,v)\in E_2 \iff (u,v)\in E \land (v,u)\in E$.

Find an algorithm that generate $H$ from $G$ in a linear time, where $G$ is represented with an adjacency list. Non linear memory is allowed.

Obviously the brute force approach won't be linear, and I thought to use an adjacency matrix but that would be at least $\Omega (n^2)$.

I also thought maybe it's possible to create a forest of DFS trees and then, checking each edge if it has an anti edge would be a lot more easier, but I'm not sure if it would be possible to keep all the information from the original graph...

Another way is to generate the anti graph of $G$, then intersect it with $G$ and then subtract the intersection from $G$, we'll be left with all edges that didn't have an anti edge, it sounds too complicated too work in linear time though and I'm not sure how to implement this algorithm..

Am I on the right track? Is there another way?

Answer 1

Here is one approach, which assumes that the adjacency lists are sorted. First, compute the reversed graph (your anti graph) in linear time. Then, compute the intersection by first merging the adjacency lists from both the original graph and the reversed graph, and then looking for edges which appear twice. This takes linear time since the lists are sorted.