If you can find Hamiltonian cycles in an undirected graph, you can find them in directed graphs too by replacing each vertex by a linear sequence of three vertices *---*---* and connect all incoming edges to one of the end nodes and all the outgoing edges to the other end node. After that you don't need to remember the direction of the edges.
For an Eulerian circuit, you need that every vertex has equal indegree and outdegree, and also that the graph is finite and connected and has at least one edge. Then you should be able to show that
- a non-edge-reusing walk of maximal length must be a circuit (and thus that such circuits exist), and
- a non-edge-reusing circuit that doesn't use all edges can always be extended, and thus that such a circuit of maximal length must necessarily contain all edges.
This type of intermediate connectivity is often called semi-connectivity.
If you used this notion you would find out that your question already has a very comprehensive answer on stackoverflow: https://stackoverflow.com/questions/30642383/determine-if-a-graph-is-semi-connected-or-not
I will sketch it here simplified though.
Idea is to reduce problem by reducing digraph G to it's graph of SCC's, say G', that is always acyclic and then try to find a path that covers all nodes in G'. If there is no such path then it's not possible to get from some SCC to some other (G' is acyclic) and that means that vertices in them have no connections. Otherwise G' is semi-connected and so is G.
Input: digraph G = (V,E)
Output: true or false if it's semi-connected
init graph G'=(V',E') from SCC's of G where V' is set of SCC of G and E' are edges between them or $E'=\{(v_1',v_2') | v_1',v_2'\in V'$ and $\exists (v_1,v_2)\in E$, $v_1 \in v_1',v_2 \in v_2'$}
// G' guaranteed to be acyclic and this can be done in O(|V| + |E|), for example, using Kosaraju's algorithm
find topological ordering $T=(v_0,...,v_{|V'|})$ of G' // correct as G' is acyclic and also can be done in O(|V'| + |E'|) using modification of DFS.
if some possible pair $(v_i,v_{i+1})$ in T is not in E' ouput false, otherwise true // if not then $(v_{i+1},v_{i})$ also is not in E' and there is no connection between vertices in $v_i$ and $v_{i+1}$, takes O(|V'|)
Best Answer
If a directed graph $D=(V,E)$ has a DFS tree that is spanning, and has in-degree equal out-degree, then it is Eulerian (ie, has an euler circuit). So this algorithm works fine.
Proof
Assume it does not have an Eulerian circuit, and let $C$ be a maximal circuit containing the root, $r$, of the tree (such circuits must exist, just start at the root and keep following edges until you get back to the root). By assumption, there is a directed edge $u\rightarrow v$ that does not belong to $C$. Since there's a DFS tree, we can pick an edge of $E(D)-E(C)$ that is incident with a vertex of $C$. To do this: follow a path $P$ of the DFS tree from $r$ to $u$, and then add the edge $u\rightarrow v$ to this path. The first edge, call it $e = x\rightarrow y$, of this path $P+(u\rightarrow v)$ that does not belong to $C$ is incident with a vertex $x$ of $C$.
Since both $D$ and $C$ have indegree = outdegree, the graph $D-E(C)$ (ie, the directed graph formed from $D$ by removing all edges of $C$) still has indegree = outegree. So starting with the edge $e$, you can find a directed circuit $C_e$ in $D-E(C)$ by just following edges until you get back to $x$.
But now the union $C\cup C_e$ is a bigger circuit, contradicting maximality of $C$!