directed graph with minimum number of chains

I have a 开发者_C百科problem but I can't figure out a solution. It goes like this:

I have a directed graph with N nodes and M links and without cycles. I need to find out the minimum numbers of chains so every node belongs to only one chain.

Example:

7 11 7 nodes; 11 links

1 2

1 5

2 3

2 5

2 7

3 4 // link exists between 3 and 4

3 6

4 6

5 4

5 6

7 3

Answer is: 2

An example is

Chain: 2-7-3-6

Chain: 1-5-4

Thanks.

He doesn't need to know if the graph is hamiltonian - knowing that it's a DAG is enough. It's probably a contest or online judge problem? It does look too hard to be homework.

Solution here: http://www2.cs.science.cmu.ac.th/person/rogaway/ps3-solns.pdf

To find the matching efficiently, consider the Hopcroft Karp algorithm: http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm