DFS by complement

Revision ru1, by _bom_bom_, 2019-03-14 14:53:08

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian _bom_bom_ 2019-03-14 17:23:57 5
ru1 Russian _bom_bom_ 2019-03-14 14:53:08 464 Первая редакция (опубликовано)