Minimum path cover in directed acyclic graph

Question

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!

Answer 1

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