Take the 2-minute tour ×

I am new to graph theory. Suppose there is a connected and undirected graph. I want to know if there is an odd length cycle in it. I can find if there is an cycle in my graph using BFS. I haven't learnt DFS yet. Here is my code which just finds if there is a cycle or not. Thanks in advance.

#define max 1000

using namespace std;

bool find_cycle(vector<int> adjacency_list[]);

int main(void)

int vertex, edge;
vector<int> adjacency_list[max];

cin >> vertex >> edge;

//Creating the adjacency list
for(int i=1; i<=edge; i++)
    int n1, n2;
    cin >> n1 >> n2;


    cout << "There is a cycle in the graph" << endl;
else cout << "There is no cycle in the graph" << endl;

return 0;

bool find_cycle(vector<int> adjacency_list[])
queue<int> q;
bool taken[max]= {false};
int parent[max];


//breadth first search
    int u=q.front();

    for(int i=0; i<adjacency_list[u].size(); i++)
        int v=adjacency_list[u][i];

        else if(v!=parent[u]) return true;

return false;
share|improve this question
Hint: a graph has no odd cycles if and only if it's 2-colorable. –  Adam Rosenfield Jul 3 '12 at 14:43
@AdamRosenfield, thanks alot. –  eddard.stark Jul 3 '12 at 14:47
@AdamRosenfield, should I search the entire graph or only the sub-graph consisting of the cycle. Because there can be more than one cycle in the graph. –  eddard.stark Jul 3 '12 at 14:50
Does this return true for every graph you throw at it by any chance? –  Wug Jul 3 '12 at 14:58
@Wug, It should return true for undirected and connected graph. But I haven't checked it for all tricky cases. –  eddard.stark Jul 3 '12 at 15:04

1 Answer 1

up vote 2 down vote accepted

The property "2-colorable" is also termed "bipartite". Whether you use DFS or BFS shouldn't matter in this case; as you visit the graph's nodes, label them 0 / 1 alternatively, depending on the color of the neighbor you came from. If you find a node which is already labelled, but labelled differently than you would label it when visiting, there is a cycle of odd length. If no such node occurs, there is no cycle of odd length.

share|improve this answer
Thanks a lot. :) –  eddard.stark Jul 3 '12 at 15:09

Your Answer


