the street network of a given city Background: Let $N$ be the street network of a given city, where each street $(A,B) \in N$ is defined to intersect at precisely two intersections $A$ and $B$ and to allow traffic directly from Intersection $A$ to Intersection $B$ in that one direction. [If two-way traffic is allowed directly between Intersections $A$ and $B$ then that is considered to be two streets between $A$ and $B$ in $N$ i.e., the street $(A,B)$ that starts at $A$ and ends at $B$, and the street $(B,A)$ that starts at $B$ and ends at $A$.]
Exercise: Now let $S$ be a minimum-cardinality set of streets such that blocking each street in $S$ eliminates all possible directed cycles. Put another way, you cannot drive away from somewhere and legally return in $N \setminus S$. [If both directions of the street between intersections A and B are blocked then that counts for two streets considered to be blocked i.e., both $(A,B)$ and $(B,A)$ are in $S$.]
Show that there is a set $S'$ of $|S|$ streets such that reversing the direction of each street $(a,b)$ in $S'$ [instead of blocking $(a,b)$ outright] also eliminates all possible directed cycles.
 A: Equivalent to the following problem: 

Let $G$ be a digraph. Let $S$ be a minimum number of arcs cut so that $G$ is a DAG. Then the graph $G'$ $=(G \setminus S) + S_R$, where $S_R = \{(x,y); (y,x) \in S\}$ is acyclic.

Proof: Suffices to give a numbering $f: V(G') \mapsto {\mathbb{Z}}$ such that $(a,b) \in E(G')$ $\implies f(b) > f(a)$. [Make sure you see why] To this end, define $f$ as follows: $f(a)$ is the longest directed path $P_a$ ending at $a$ in $G \setminus S$ [$P_a$ is not necessarily maximal, there in turn may be arcs outgoing from $a$].
Then clearly $f$ already satsifies the following: $(x,y) \in E(G \setminus S) \implies f(y) > f(x)$. It now suffices to show that $(b,a) \in S_R$ implies that $f(b) < f(a)$. We do this next. As $S$ is minimal for each $(a,b) \in S$ there is a dipath in $G \setminus S$ from $b$ to $a$ [make sure you see why]. Thus indeed $f(b) > f(a)$. Thus the mapping $f: V(G') \mapsto {\mathbb{Z}}$ indeed has the property that  $(a,b) \in E(G') \implies f(b) > f(a)$, and so the result follows.
