set of vertex-disjoint cycles so that each vertex belongs to a cycle

Question

Here I have a directed graph G. I need to to determine whether there exists a set of vertex-disjoint cycles so that each vertex belongs to a cycle.

I'm not sure if this can be done in polynomial time or if its NP-Complete? Can anyone atleast point me in the right direction?

Answer 1

Split each vertex into an "in" vertex and an "out" vertex. Then a vertex-disjoint cycle cover corresponds to a perfect matching on this graph. You can find out the answer to your question as fast as you can find perfect matchings (i.e. polynomial time)