ориентированный граф с минимальным количеством цепочек

Question

У меня есть проблема, но я не могу найти решение. Это выглядит так:

У меня есть ориентированный граф с N узлами и M связями и без циклов. Мне нужно выяснить минимальное количество цепочек, чтобы каждый узел принадлежал только одной цепочке.

Пример:

7 11 7 узлов; 11 ссылок
1 2
1 5
2 3
2 5
2 7
3 4 // ссылка существует между 3 и 4
3 6
4 6
5 4
5 6
7 3

Ответ: 2

Примером является
Цепочка: 2-7-3-6
Цепочка: 1-5-4

Спасибо.

Answer 1

Ему не нужно знать, является ли график гамильтоновым - достаточно знать, что это DAG. Вероятно, это проблема конкурса или онлайн-судьи? Это выглядит слишком сложно, чтобы быть домашней работой.

Решение здесь: http://www2.cs.science.cmu.ac.th/person/rogaway/ps3-solns.pdf

Чтобы эффективно найти соответствие, рассмотрим алгоритм Хопкрофта Карпа: http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm