POJ 2942 - Knights of the Round Table
Problem : Find the number of vertices in Graph such that there is no odd cycle contain it.
Solution : For each vertice-bi-connected set, if there is a odd cycle, all the vertices in that set are in some odd cycle. Check all the vertice-bi-connected set, the number of all remaining vertices is the answer.
Proof :
1. If a vertice-bi-connected set has odd cycle, actually each point has two vertice-distinct path to that cycle's two disjiont vertice (see note), thus connect the two path in either of the odd cycle path will get another odd cycle.
2. If a vertice is in a odd cycle, it must be in a vertice-bi-connected set. (Obviously).
3. The way to get an odd cycle in vertice-bi-connected set : Do the bfs at any vertice in that set, and if there is a edge connect the same depth of two vertices, then there are. Otherwise there's not. (proof: After bfs, the edge not in the bfs tree connect two vertices with depth differece in tree at most 1).