Given a connected graph with edges >= vertices, find an algorithm in O(n + m) that orients the edges such that every vertex has indegree of at least 1
Start with any vertex $v_s$, and do a BFS from that $v_s$ to discover the entire graph.  When you traverse an edge, you orient it away from the start node.

Now every vertex $v \in V \setminus \{v_s\}$ has $\deg_{\text{in}}(v) &gt; 0$.

Find a path from $v_s$ to any vertex $v_t$ such that $\deg_{\text{in}}(v_t) \geq 2$.  Since the input graph is not a tree, such a vertex must exist.

Flip all edges in the path.

This graph satisfies your requirement since 


every internal vertex $v_i$ in the path still has $\deg_{\text{in}}(v_i) &gt; 0$,
$v_t$ now has $\deg_{\text{in}}(v_t) \geq 1$ (it decreased by one), and
$v_s$ has $\deg_{\text{in}}(v_s) &gt; 0$.


Running time: $O(n + m)$.