[Solved]: Linear-time algorithm to find an odd-length cycle in a directed graph

Problem Detail: 

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.)

---

The related post@cs.stackexchange asks for the existence of an odd-length directed cycle in a digraph, which is solved by the following theorem@algs4.cs.princeton.edu.

Theorem: A directed graph has an odd-length directed cycle if and only if one (or more) of its strong components is non-bipartite (when treated as an undirected graph).

Thus, we can assume that the digraph is strongly connected.

Asked By : hengxin

Answered By : Denis Pankratov

Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never seen an edge $(u,v)$ that goes between levels of the same parity then $G$ is bipartite. The parity of the level of $u$ defines the partition that $u$ belongs to. Note that since every vertex is reachable from $s$, BFS will explore all the edges, so all of the edges would be going between the two blocks of the partition. Otherwise, you find an edge $(u,v)$ that goes between levels of the same parity. Suppose level of $u$ is even and level of $v$ is even. Then run DFS (or BFS) from $v$ to get a path to $s$. If this path is of even length then you get an odd directed cycle $s \rightsquigarrow u \rightarrow v \rightsquigarrow s$. If this path is of odd length then you get an odd directed cycle $s \rightsquigarrow v \rightsquigarrow s$. Analogous thing holds when level of $u$ is odd and level of $v$ is odd. Since this algorithm simply does 2 runs of BFS/DFS, it runs in linear time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57565