Partitioning graph edges into two cycleless sets

Question

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The algorithm needs to run in $O\left(V+E\right)$.

I've tried running a depth-first search on $G$ and trying to somehow partition the cross, back, and forward edges into cycleless sets, but this approach hasn't gotten me very far. I've tried looking at specific graph examples and finding specific solutions to the problem, but I haven't been able to generalize these solutions into an algorithm.

The homework tag seems to have been removed - this is a homework question so I'd appreciate hints rather than an outright solution.

EDIT: I think I may have solved it, but I'm having a difficult part formalizing a certain part of it.

Assume the graph is connected (otherwise just run the algorithm on each separate component). Take $v\in V$, and let $T=(V,E')$ be the tree computed by $DFS(v)$. Define $B$ to be the set of back edges, $F$ to be the set of forward eges, and $C$ to be the set of cross edges.

We define $E_1 = E'\cup F$, which clearly has no cycles.

$E_2$ will contain the back edges, and now we have to divide the cross edges in a manner such that they won't form a cycle. Intuitively I want the cross edges that "go left" to go into $E_1$ and the cross edges that "go right" to go into $E_2$ but I don't know how to formalize it, or if it's even correct.

Answer 1

It seems like things would be easier if you had no cross edges at all. Maybe you can modify your spanning-tree idea to make that happen.

Answer 2

Lay the vertices out in a line $ 1, 2, 3, \ldots $. Put all the rightwards arcs in $E1$ and all the leftwards arcs in $E2$.

For $ V = \{ v_1, v_2, \ldots v_n \}$, for $ <v_i, v_j> \epsilon \ G $,

$$ <v_i, v_j> \epsilon \ E_1 \iff i < j \\ <v_i, v_j> \epsilon \ E_2 \iff i \ge j $$