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

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?