# 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

I'm not exactly sure how to approach this problem. I was thinking we would need to detect a vertex in a cycle, then run DFS on it while also orienting the edges along each vertex u in the cycle, to be directed from u to some vertex v incident to it. But I am not sure what edges cases I might be overlooking, or whether the idea is sufficient. Below is one such example. Step 1. Find any spanning tree $$T$$ for the graph $$G=(V,E)$$. Number of its edges is $$|V|-1$$.

Step 2. Find any edge $$\{u,v\} \in E$$, which doesn't belong to the tree $$T$$. It can be done because $$|E| \ge |V|$$.

Step 3. Choose the vertex $$v$$ as "root" for the tree $$T$$ and orient all the edges in the tree $$T$$ "from" this root.

Step 4. Orient the edge $$\{u,v\}$$ from the vertex $$u$$ to the vertex $$v$$. Arbitrarily orient all the remaining edges, which aren't oriented yet.

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) > 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

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

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