StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhat is odd length cycle and how can I know if there is an odd cycle in my graph?
text
Body
copied!<p>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.</p> <pre><code>#include<iostream> #include<vector> #include<queue> #include<cstdio> #define max 1000 using namespace std; bool find_cycle(vector<int> adjacency_list[]); int main(void) { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); 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; adjacency_list[n1].push_back(n2); adjacency_list[n2].push_back(n1); } if(find_cycle(adjacency_list)) 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]; q.push(1); taken[1]=true; parent[1]=1; //breadth first search while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0; i<adjacency_list[u].size(); i++) { int v=adjacency_list[u][i]; if(!taken[v]) { q.push(v); taken[v]=true; parent[v]=u; } else if(v!=parent[u]) return true; } } return false; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload