Finding cycle path in directed graph

See more:

C++

recursion

graph

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:

Graph{
    private:
        int V;			// No. of vertices
        list<int> *adj; // Pointer to array containing adjacency lists
        ...
    };
          

    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;
            for (i = adj[v].begin(); i != adj[v].end(); ++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;
    }