CODEWITHSUNDEEP
algorithmlanguage-agnostic
user273386
user273386

Reputation: 35

directed graph with minimum number of chains

I have a 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.

Upvotes: 3

Views: 610

Answers (1)

IVlad
IVlad

Reputation: 43487

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

Upvotes: 2

Related Questions