Finding odd directed circuit

I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph.

Can anyone help me how to proceed with this problem???

Firstly:


König's Theorem (1936): A graph is 2-colorable iff it has no circuits of odd length.


― www-math.ucdenver.edu

Also:

• A graph is bipartite if and only if it does not contain an odd cycle.

• A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).

― wikipedia

So we see we are looking for a 2-colorable graph, or a bipartite graph. These are all the same thing.

Edit:


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


― algs4.cs.princeton.edu

Since your graph is strongly connected, we can treat it as an undirected graph and test for bipartiteness using the regular testing algorithms.

The wikipedia article gives an example algorithm to test bipartiteness using Breadth First Search. A presentation explaining the algorithm is available from The University of Maryland website.

StackExchange Computer Science Q#3517, answer score: 9