Let $G=(V,E)$ be a digraph. We call it "cyclable" if there exists $k$ $\geq$ 1 circuits in $G$,$C_1$,...$C_k$, of which sets of vertices, V($C_1$),...,V($C_k$) , makes a partition of $V(G)$.
I must prove that:
We can test in polynomial time (in terms of $|V| + |E|$ ) whether a digraph $G=(V,E)$ is cyclable, solving a problem of maximum flow value in a network of flows convenient built.
The property of "cyclable" is easy to understand, but I have problems on the second part of the problem.
We must test that property using a maximum flow problem.
I tried to construct a network, and find a flow and check every vertex to see what flows it gives. Is this a good idea to start? And how do i continue?