Покрытие вершин орграфа циклами

[KappaGolden]

Пусть дан ориентированный граф $G$. Как найти в нём некоторое множество циклов, которые попарно не пересекаются, но покрывают всё множество вершин, если цикл из одной вершины не считается циклом, но цикл из двух вершин - считается?
Асимптотика: $O(nm)$.

У меня была мысль о том что, можно преобразовать эту задачу в задачу поиска совершенного паросочетания в большем графе, но совершенно неясно как это вообще можно сделать...

[svv]

А если в графе нет циклов? или циклы есть, но они не покрывают всё множество вершин? Или покрывают всё множество, но при этом пересекаются?
Кстати, общая вершина тоже считается пересечением?

P.S.
KappaGolden
Вы видели в Википедии статью Покрытие вершин циклами? Там есть ссылка
http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problem 1),
и в ней объяснение, как свести задачу о покрытии вершин орграфа циклами к поиску совершенного паросочетания (на англ.языке).

[KappaGolden]

Предполагается, что такое покрытие есть

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:


- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.