We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I tried a variant of BFS where instead of creating the edges of the complement, each time I search the pe (primary edges) and take for j in notdiscovered where (i,j) != pe and (j,i) != pe.
notdiscovered starts with all vertices.
Instead of adding to discovered, I discard from notdiscovered. I found it was essential to do while q and notdiscovered. notdiscovered becomes empty very fast, and then everything is found already. Without that, it times out.
Rust & Murderer
You are viewing a single comment's thread. Return to all comments →
I tried a variant of BFS where instead of creating the edges of the complement, each time I search the pe (primary edges) and take for j in notdiscovered where (i,j) != pe and (j,i) != pe. notdiscovered starts with all vertices. Instead of adding to discovered, I discard from notdiscovered. I found it was essential to do while q and notdiscovered. notdiscovered becomes empty very fast, and then everything is found already. Without that, it times out.