Skip to content

Instantly share code, notes, and snippets.

@arkanath
Created September 24, 2014 12:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save arkanath/4f1c3f6b2fe81200e7dd to your computer and use it in GitHub Desktop.
Save arkanath/4f1c3f6b2fe81200e7dd to your computer and use it in GitHub Desktop.
Depth First Search, Recursive with Cycle Detection
vector<int> adjList[N];
int visited[N];
bool dfsrecursiveandcycle(int u, int parent)
{
cout << "visited " << u << endl;// :-)
visited[u] = 1;
bool ans = false;
for(int i=0;i<adjList[u].size();i++)
{
if(!visited[adjList[u][i]])
{
if(dfsrecursiveandcycle(adjList[u][i], u)) ans = true;
}
else if(adjList[u][i]!=parent)
{
ans = true;
}
}
return ans;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment