HINT: Use bipartite matching
I have to find a cycle cover of a directed graph G or report none exists. A cycle cover - a set of disjoint cycles covering all vertices of G.
**MY idea: a) Since G is NOT bipartite (given), we create a bipartite graph H (with two vertex sets -= Vl and VR) ** b) then we add the edge from G to the bipartite graph H - find the matching in H corresponding to the cycle cover in G.
There's a cycle cover if and only if for each vertex v, there's only ONE edge leaving and entering v
So time taken would be O(mn)