PROBLEM LINK:Author: Roman Rubanenko DIFFICULTY:Medium PREREQUISITES:Graph Theory, topological sort PROBLEM:Given a DAG(directed acyclic graph). Find out maximum number of edges that can be added into it so that it still remains a DAG. If there are multiple solutions which lead to same maximum number of edges that can be added, then you should output the lexicographically smallest sequence of edges. ExplanationLet's go step by step, How to find count of maximum number of edges? Oh, it is easy, You know that graph is a DAG, so there is some topological ordering of a graph. We can add an edge from any vertex u to v (v lies after u in topological ordering). Note that if the the edge (u, v) already exists, then we won't add it. But wait, you have not proved that the these number of edges which you are adding will be maximum. Yes, you are right. Let us prove this claim. But adding such an edge will create a cycle, because edge (u, v) is already there. Let me also give a simpler proof (due to Shiplu): First of all, one can show that there can't be more than C(n,2) edges by pigeon hole principle. Then we can show that any topological sort gives us these C(n,2) edges. Nice idea, But still, you have only proved the maximal part, not the maximum part. Oh, ok. I will now prove that the maximal set above generated is the indeed one of the maximum sets. We will prove it by contradiction. Let us assume that we have added edges in some other way such that (i.e. our DAG is not same as maximal DAG) it contains more edges than the above maximal set of edges. Now, note that as graph is still a DAG, we can do a topological ordering of this. Note that in the topological order of graph, there can not be any edge from v to u (v lies after u) (from the definition of topological ordering). Only edges we can have, lie in the topological direction. But then it can not have more edges than the maximal set, because maximal set also contains all the edges going in topological direction. Hence it leads to contradiction. Nice proof, I got it :) Only thing remaining now is to figure out the lexicographically smallest part, I have some idea about it. What if I take any topological ordering and add edges in the topological direction. Oh, this strategy is wrong. Consider the following DAG. A valid topological sorting is 2 > 3 > 1. So you will try to add edges between (2, 3), (2, 1) and (3, 1). Edge between (3, 1) is already in the DAG. So we will add edges between (2, 3) and (2, 1). But there is a better way of adding edges, add edges (1, 2) and (3, 2). This sequence is lexicographically smaller than previous. Yes, my bad. Let me propose another strategy. Start from the vertices with index = 0, (As the graph is DAG, there should be atleast one such vertex). If there are more than one vertices having indegree zero, pick the vertex having minimum number. Now from this vertex, add the edges to all the vertices in the current DAG. Remove the vertex from the DAG and update the indegree of the vertices which are attached to it. Keep doing the same until all the vertices are taken. Nice strategy, but alas. This is also wrong. Infact, it wont even work on the previous DAG. First we will pick vertex 2(because 2 and 3 are with indeg = 0, but 2 is lower number than 3). Now we will add edges between (2, 1) and (2, 3). Then we will remove 2. Our new DAG will remain only of a single edge (3, 1). So we can not add any more edges. But as said earlier, adding edges (1, 2) and (3, 2) is better than this. I am out of idea, Please help me in finding the right strategy Let us do similar thing as you did. But we will do it from the end to the beginning. Let's take a vertex that has no outcoming edges as the last one (i.e one with the outDegree zero) If there is more then one such vertices, then pick one with bigger number. Now add edges from all the vertices in the current graph to this vertex. Then delete this vertex from the DAG, and keep doing this until the graph is empty. I did not get much, Can you please take an example? Of course, Let us consider the previous DAG. Initially both 1 and 2 are vertices with outDegree zero. We will pick 2 because have bigger number than 1. Now we will add edge (1, 2), (3, 2). Now we will delete vertex 2. Now the graph contains a single edge (3, 1). We will pick 1 (only having outDegree 0). We will try to add (3, 1), but it is already there, so won't readd it. But how to prove that this is the lexicographically smallest sequence of edges? Okay, here we go. If we chose a vertex v with outdegree 0, we can add as many edges (u, v) where u is unused. So there is no chance of cycle. Now we will prove the lexicographical part by contradiction. Suppose that there are two vertices u and v ( u < v) with outdegree 0 and we are claiming that if we chose u before v than we will get lexicographically smallest sequence of edges. Suppose there is another vertex w (u < w < v). Now there is a chance that the edge from w to u will be chosen but if we would have chosen v then there will be chance that the u > w will be chosen. If not, then there is no way to to chose it. Nice proof, I got it. Now how to implement it, Can you please give some pseudo code? Yes. Let us have its pseudo code. Pseudo Code Let us do the complexity analysis now Complexity: So we are doing n such iterations. Each iteration takes O(n) time. So overall time complexity is O(n^2). AUTHOR'S and TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 21 Jul '14, 01:02

Very simple and excellent editorial. Learnt a lot from this. Thanks Praveen.. :) answered 21 Jul '14, 22:56

'Start from the vertices with in degree = 0' instead of 'Start from the vertices with index = 0' I suppose. I have used similar idea but got WA during contest. Can you give some test case , here is my solution answered 21 Jul '14, 03:54

can someone tell me whats wrong with this approach
answered 21 Jul '14, 10:24

Is there any corner case becuase my code is running till 0.8 sec and then gives WA. answered 22 Jul '14, 03:25

Simply amazing editorial ..hats off LoneCoder answered 30 Jul '14, 00:08

consider following case; 5 01001 00100 00010 01000 01100 output; 3 1 3 1 4 4 5 can any one pls suggests whats wrong in this analysis,,, answered 06 Dec '15, 12:43
