I have seen two implentation of DFS that people generally use.
bool visit[N];
int par[N];
vector<int> g[N];
void dfs1(int v)
{
visit[v] = true;
for(auto child : g[v])
{
if(!visit[child])
dfs1(child);
}
}
void dfs2(int v, int p)
{
par[v] = p;
for(auto child : g[v])
{
if(child == par[v])
continue;
dfs(child,v);
}
}
What is the difference between these two implementations? Is the second implementation only used when we need parent or some other cases also. I always maintain visit array, but some people don't does it affect. I think it should cause infinite recursion but it doesn't.
Can someone please explain it in details.