15,561,817 members
See more:
I am making a directed Graph class. I want find if there is any Euler Cycle and update a vector with it's path accordingly. My Function some times work but others add two times the last edge of the path.So i guess it needs to be tydied up. (If others parts of my code are too simple, so I didn't include them)

Example:
having a Graph with these paths

> 0->1, 0->2, 1->2, 2->3, 3->4, 4->0, 4->6, 1->5, 5->6

should set the vector to `[0 2 3 4 ]` or anything else valid.

I can obviously do something like this:
`if (path.end()[-2]==path.end()[-1]) path.pop_back();`
but I don't like it and still I don't understand why this occurres .

What I have tried:

C++
```Graph{
private:
int V;			// No. of vertices
...
};

bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack, vector<int> &path) const {
if (visited[v] == false) {
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
if (!visited[*i] && isCyclicUtil(*i, visited, recStack, path)){
path.push_back(*i);
return true;}
else if (recStack[*i]){
path.push_back(*i);
return true;}
}
}
recStack[v] = false; // remove the vertex from recursion stack
path.pop_back();
return false;
}

bool Graph::cycle(vector<int> &path) const {
// Mark all the vertices as not visited and not part of recursion stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different DFS trees
for (int i = 0; i < V; i++){
path.push_back(i);
if (isCyclicUtil(i, visited, recStack, path)) {
reverse(path.begin(),path.end());
//path.pop_back();
return true;
}
path.clear();
}
path.clear();
return false;
}```
Posted
Updated 7-Jun-18 7:14am
v2