I need help. I can't understand how to fast enough do DFS on the complement graph of some graph $$$G=(V, E), |V| = n, |E| = m$$$, where $$$n, m$$$ is order by $$$10 ^ 5$$$.

I can come up with $$$O(n k \log m)$$$ algorithm, where $$$k$$$ is amount of reachable nodes from start node. It is easy to understand that the worst case takes $$$O(n ^ 2 \log m)$$$ time. it seems there is $$$O((n + m) \log m)$$$ algortihm.

Also we can eliminate $$$\log$$$ using universal hashing.