Problem statement : Given a degree sequence D. Can we create a simple graph (graph without self loops and parallel edges) from D?
This is a classical problem that can be solved by using Havel-Hakimi algorithm or Erdős–Gallai theorem. Both of them have time complexity O(n^2). But I have found a task with N <= 100000 which is incompatible with O(n^2) algorithms. Is there any faster method to solve this?
(Edited) There are no any special conditions in this task
(Edited) Solved!! Optimize Erdős-Gallai Algorithm by using binary search to find min(di,k) of each k efficiently. New time complexity is O(n log n). Thanks 300iq and animeshf for this idea!
Link for Erdős-Gallai algorithm : https://en.wikipedia.org/wiki/Erdős–Gallai_theorem
Thanks everyone for replying.
Gale-Ryser may work if your graph is bipartite.
Thanks for reply. But for now, I cant find any special conditions in this task.
Havel Hakimi can be implemented in such a way so that the complexity becomes O(Summation of degrees of all nodes * log(n)) which can be smaller than O(n^2) depending on the input constraint. What is the constraint on the degrees of the nodes in your problem?
Sadly, It seems there is no special condition about this too.... ;( All degrees can be at most N.
I guess you have to output the edges, so sum(degrees) can't be too large, because you have to print out 2*sum(degrees)/2 numbers, which would be impossible for numbers like > 10^7.
Maybe YES/NO task.
Yes,and there are 10 queries per test case. Time limit is just 1 sec.
So you can check Erdos-Gallai theotem with binary search and partial sums
That looks cool! I completely forgot about binary search. I will try this soon.
Auto comment: topic has been updated by comtalyst (previous revision, new revision, compare).
Seems like some people wrote a paper on optimizing Erdős-Gallai from O(n2) to O(nlogn) (or O(n) if D is already sorted). The relevant part is the 15 line pseudocode on page 6 (It is pretty self-explanatory).
Auto comment: topic has been updated by comtalyst (previous revision, new revision, compare).
Can you share the problem link?
This problem come from a thai competitive programming site named CodeCube. Here is the problem link.
Unfortunately, official problem description and the whole site is in Thai only (but it isnt hard to be analyzed). And you will have to register before submit.
Here is my brief English translation: Given Q — number of queries (Q <= 10). Each query contains N — number of vertices in the graph (N <= 100000) followed by a degree sequence, each of them doesnt exceed N. For each query, answer "Yes" or "No".