Let's see how good /sci/ is with graphs. This is an original problem, so I doubt you'll be able to find the answer online. Will post the answer in 8-ish hours if no one has solve it by then.
You are given the complement of a nearly-complete unweighted undirected simple graph with $$N$$ nodes. By nearly-complete we mean that the graph has $$ N(N-1)/2 - M $$ edges, where $$M <= N^1.5$$. So you are given those $$M$$ missing edges, as well $$Q<=N^1.5$$ queries. Each query is a pair of nodes and you have to find the length of the shortest path between them (or say there is no path).
What is the best solution you can come up with, in terms of time (and memory) complexity?
You are given the complement of a nearly-complete unweighted undirected simple graph with $$N$$ nodes. By nearly-complete we mean that the graph has $$ N(N-1)/2 - M $$ edges, where $$M <= N^1.5$$. So you are given those $$M$$ missing edges, as well $$Q<=N^1.5$$ queries. Each query is a pair of nodes and you have to find the length of the shortest path between them (or say there is no path).
What is the best solution you can come up with, in terms of time (and memory) complexity?
