i am getting TLE but the complexity of my code is O(N^2). Can anyone please suggest me some test case where i am lacking !
my approach : at first i tried to join all the d*n edges (taking a set of d vertices each time and then the remaining vertices(those which didn’t form a set of d vertices) starting with the uppermost vertices). And then tried to add the edges across the sets(as all the edges within the same set are already joined) and as all the vertices above the “curr” have reached their maximum limit, so, i just consider the sets below the current one.
The question is a easy one. What you must do is, to device an algorithm to make bi-partite graph.
A sure-shot algorithm is this-
Checking if a graph is possible or not can be done in O(1) time.
If its possible-
First make d edges to satisfy minimum degree. I did it by giving edges like, 1 to 1, 1 to 2, 1 to 3…1 to d. Then 2 to 2, 2 to 3, 2 to 4…2 to d+1. In case we exceed n, we take %n. Eg, edges of n-1 are - n-1 to n-1, n-1 to n, n-1 to 1, n-1 to 2… and so on till d edges.
Now for every remaining edge, take a vertex and give it as many edges as you can. Eg- Lets take vertex 1 for example. We gave edges of 1 to 1, 1 to 2,…1 to d. Now we will give it as many edges as possible, i.e. 1 to d+1, 1 to d+2, …1 to D. We stop when either there are no more edges, or 1 gets degree D. If 1 gets degree D and more edges remain, we simply go to next vertex and carry on. Eg- lets say 1 got degree D. Now we come at vertex 2. It had edges 2 to 2, 2 to 3…2 to d+1. We give edges in pattern 2 to d+2, 2 to d+3…2 to D+1. (Note- If you add edges in way like 2 to 1, then 2 to d+1, 2 to d+2… then it will give WA, because in cases you will exceed D for vertex 1 this way. Its crucial to start adding vertex from where we left off after satisfying the degree d.)