Orientations with single source and sink (Q1057281)

Given a graph G and a pair of vertices s and t, linear time algorithms are formulated for finding orientations D of G such that D has a unique source s and sink t, i.e., D has unique vertices s and t of zero indegree and zero outdegree, respectively. The additional requirement that D be acyclic is also considered. Necessary and sufficient conditions for the existence of the orientations are given.