Minimum path cover in directed acyclic graph
algorithm, graph
Solution
I found the answer myself , the next day i posted this question.
And my-solution passed all test cases .
I was making mistake in the last step. Actually the Answer/solution is the total Number of vertices in SET B that does not contain the edge of Maximal Bipartite Matching.
For Example on sample test case 1::
Maximal Matching M={(1A,3B)}.
No edge of maximal matching is incident upon two vertices (Vertex 1 and Vertex 2).So answer is equal to number of such vertex=2
For test case 2::
Maximal Matching M={(1A,2B),(2A,3B),(3A,4B),(4A,5B)}.
No edge of maximal matching is incident upon one vertex (Vertex 1).So answer is equal to 1
Problem
The question I am going to ask here has already been asked before in stack overflow. But I am not able to understand properly the solutions posted by Skiminok. Here is the Link . I tried the solution posted on the above link with the given two sample test-cases ,but i am not able to get the correct answer. For the test case 1:: N=3 and K=2 5 4 7 The DAG will be:: Note :I have constructed the above DAG Considering: Let pi and pj be two different problems. Then we will draw a directed edge from pi to pj if and only if pj can be solved directly after pi on the same day, consecutively. Namely, the following conditions have to be satisfied: i < j, because you should solve the less difficult problem earlier. |vi - vj| >= K (the rating requirement). Then I constructed the Bipartite graph considering:: For each directed edge (u, v) of the original DAG one should add an undirected edge (au, bv) to the bipartite graph, where {ai} and {bi} are two parts of size n. The answer =maximum cardinality matching in above bipartite graph . maximum cardinality matching in above bipartite graph =1 (Green colored egde) But the answer is 2. Similarly Sample Test Case 2: 5 1 5 3 4 5 6 The MAx cardinality in above graph is MORE THAN ONE ,but the Correct answer is 1. I think i am not implementing it correctly,please can you tell where i am making mistake Or is there any other Method Thanks!