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?