15,741,818 members

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 .C++

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; }

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900